SRM 659 Div1 ApplesAndOrangesEasy

contents

1. 1. Problem
2. 2. Solution

Problem

給定長度為 $N$ 個序列，在這序列中表示吃蘋果或者是橘子的順序，必須保證的是任意連續區間長度為 $K$ 中，最多只會吃 $K/2$ 個蘋果，已知部分位置一定是蘋果，請問序列中最多有幾個蘋果。

Solution

嘗試要用 $O(N)$ 的貪心解法，弄了快一個小時沒出來。弄 $O(N^2)$ 做一下就過，從尾端開始往前掃，來決定未知的地方 $i$ 是否要放蘋果，假若後綴 $[i, i+K-1]$ 的蘋果樹，如果總量小於限制將這個地方設置為蘋果，反之超過，將最鄰近的 蘋果全部取消到符合規定。

#include <stdio.h> 
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
class ApplesAndOrangesEasy {
public:
    int maximumApples(int N, int K, vector<int> info) {
        const int MAXN = 4096;
        int A[MAXN] = {}, apple = K/2;
        int ret = (int) info.size();
        memset(A, -1, sizeof(A));
        for (int i = 0; i < info.size(); i++)
            A[info[i]] = 1;
        for (int i = N+1; i <= N + K; i++)
            A[i] = 0;
        for (int i = N; i >= 1; i--) {
            int sum = 0;
            for (int j = i; j < i+K; j++)
                sum += A[j] >= 1;
            if (sum < apple && A[i] == -1)
                A[i] = 2, ret++, sum++;
            if (sum > apple) {
                for (int j = i; j < i+K; j++) {
                    if (sum > apple && A[j] == 2) {
                        A[j] = -1, ret--, sum--;
                    }
                }
            }
        }
        return ret;
    }
};
int main() {
    ApplesAndOrangesEasy ap;
    int a[] = {1, 3};
    ap.maximumApples(3, 2, vector<int>(a, a + 2));
    return 0;
}