【AtCoderBeginnerContest121 C】勝つために苦手な剣を手に取ることにした話
スポンサードリンク
https://atcoder.jp/contests/abc121/tasks/abc121_c
問題
栄養ドリンクが売られている店は 軒あり、 軒目の店では 本 円の栄養ドリンクを 本まで買うことができます。
最小で何円あれば 本の栄養ドリンクを買い集めることができるでしょうか。
考え方
安い方から買う。
安い順番にソートして、
その店の在庫がほしい数に満たなかったら全部買って次の店へ。
十分な数の在庫がある店では、ほしい数だけ買って終わり。
int型では足りないことに注意しながら、かかったお金を計算する。
書いたコード
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
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++を覚えて、使って、勝ちたい。
いろいろ考えた結果、僕は勝利のため、苦手な剣の使い方を覚えることにします。
スポンサードリンク