WARush

SRMの結果とか、解けた問題のコードを書いていきます

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;
    }
};