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]$ 的蘋果樹,如果總量小於限制將這個地方設置為蘋果,反之超過,將最鄰近的 蘋果全部取消到符合規定。

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