https://atcoder.jp/contests/abc121/tasks/abc121_c

問題

栄養ドリンクが売られている店は $N$ 軒あり、$i$ 軒目の店では $1$ 本 $A_i$ 円の栄養ドリンクを $B_i$ 本まで買うことができます。

最小で何円あれば $M$ 本の栄養ドリンクを買い集めることができるでしょうか。

考え方

安い方から買う。

安い順番にソートして、

その店の在庫がほしい数に満たなかったら全部買って次の店へ。

十分な数の在庫がある店では、ほしい数だけ買って終わり。

int型では足りないことに注意しながら、かかったお金を計算する。



書いたコード

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

public class State

{

 

    public struct AB

    {

        public int A;

        public int B;

 

        public AB(int a,int b)

        {

            this.A = a;

            this.B = b;

 

        }

    }

 

    public static void Main()

    {

        int N, M;

        var split = Console.ReadLine().Split().Select(int.Parse).ToArray();

        N = split[0];

        M = split[1];

        AB[] ab = new AB[N];

        for (long i = 0; i < N; i++)

        {

            split = Console.ReadLine().Split().Select(int.Parse).ToArray();

 

            ab[i] = new AB(split[0], split[1]);

        }

        Array.Sort(ab,comparer);

        long store = 0;

        int need = M;

        int[] buy = new int[N];

 

        while (need >0)

        {

            if (ab[store].B <= need)

            {

                buy[store] = ab[store].B;

                need -= ab[store].B;

                store++;

            }

            else

            {

                buy[store] = need;

                break;

            }

        }

        long pay = 0;

        for (int i = 0; i < N; i++)

        {

            if (buy[i] == 0) break;

            long temp = ab[i].A;

            temp *= buy[i];

            pay += temp;

        }

        Console.WriteLine(pay);

 

    }

 

    public static int comparer(AB a,AB b)

    {

        if (a.A > b.A) return 1;

        else return -1;

    }

}

解説を読んだ

おなじようなことが書いてありました。

結果

TLEしました(Time Limit Exceeded、制限時間オーバー)。



考えは間違っていないはずで、長めのコードでのみTLEしているので、もしかしたら無限ループに陥ってるかもしれないのが恐ろしいところです。補導しないで。



未だに、何が時間くってるのかわかりません。解説にはソートがネックになりますと書いてあったんですが。





今まで、Unityで使えるから、mallocしなくていいから、配列を関数の返り値に使える（使いやすい）から、文字列の同値判定にequalsとかじゃなくて==が使えるから、C# を使ってきました。



でも、勝ちたい。早いC++を覚えて、使って、勝ちたい。





いろいろ考えた結果、僕は勝利のため、苦手な剣の使い方を覚えることにします。