[COCI2011-2012#4] ZIMA

Zirnc

2022-01-28 23:09:47

Solution

一道简简单单的模拟题。。 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; } ```