[COCI2011-2012#4] ZIMA
Zirnc
2022-01-28 23:09:47
一道简简单单的模拟题。。
1. 首先求出每一个冰期,记其起点为 $s$,长度为 $T$。
2. 然后用一个布尔数组计数,对于每一个冰期先标记来临之前 $2T$ 天(即为 $[s-2T, s)$)的警示状态。
3. 最后枚举每一个长度为 $T_{max}$ 的冰期,求出它们 $[s-3T, s-2T)$ 区间内新增的警示的天数的最大值,和第二步求出的警示天数相加即为答案。
```cpp
#include <bits/stdc++.h>
using namespace std;
int n, t[100005];
struct node {
int s, t;
};
bool cmp(node a, node b) { return a.t > b.t; }
vector<node> tv;
int sum[100005];
bool b[100005];
int main() {
scanf("%d", &n);
int prev = -1;
// Step 1.
for (int i = 1; i <= n; i++) {
scanf("%d", &t[i]);
sum[i] = sum[i - 1];
if (t[i] < 0) {
if (prev == -1)
prev = i;
} else {
sum[i]++;
if (t[i - 1] < 0) {
int curt = i - prev;
tv.push_back({prev, curt});
prev = -1;
}
}
}
if (t[n] < 0)
tv.push_back({prev, n - prev + 1});
sort(tv.begin(), tv.end(), cmp);
// Step 2.
int ans = 0, ans2 = 0;
for (int i = 0; i < tv.size(); i++) {
for (int j = max(1, tv[i].s - tv[i].t * 2); j < tv[i].s; j++) {
if (b[j] == 0)
ans++;
b[j] = 1;
}
}
// Step 3.
for (int i = 0; i < tv.size(); i++) {
if (tv[i].t < tv[0].t)
break;
int cnt = 0;
for (int j = max(1, tv[i].s - tv[i].t * 3);
j < max(1, tv[i].s - tv[i].t * 2); j++) {
if (b[j] == 0)
cnt++;
}
ans2 = max(ans2, cnt);
}
printf("%d\n", ans + ans2);
return 0;
}
```