SRM659 Div1 Easy "ApplesAndOrangesEasy"
考えたこと
貪欲でいけそう。n回目の買い物の時に、リンゴを買っても大丈夫ならば、買っちゃうのが最善。
しゃくとり法っぽくi回目からi - K回目の範囲のリンゴの総和の計算し、総和がK / 2未満であるのことがK回以上続いたときに、i - K + 1回目にリンゴが買えることになる。(めちゃくちゃ分かりづらいけど)こうするとO(N)で次にリンゴを買うべき回数が判明し、全体としてはO(N^2)でいける。
ソースコード
bool apple[4100]; // リンゴを買うことが確定したらture class ApplesAndOrangesEasy { public: int maximumApples(int N, int K, vector <int> info) { int ans = 0; memset(apple, 0, sizeof(apple)); for (int i = 0; i < info.size(); i++) { apple[info[i] - 1] = true; ans++; } while (true) { bool find = false; int sum = 0; int cnt = 0; for (int i = 0; i < N + K - 1 && !find; i++) { int add = 0; if (apple[i]) add++; if (i - K >= 0 && apple[i - K]) add--; sum += add; if (sum < K / 2) { cnt++; } else { cnt = 0; } if (cnt >= K && !apple[i - K + 1]) { // 買うべき! apple[i - K + 1] = true; find = true; ans++; } } if (!find) break; } return ans; } };