[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) 区间内新增的警示的天数的最大值，和第二步求出的警示天数相加即为答案。

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