题解 P6015 【游戏】

· · 题解

发一个我比赛时瞎搞的做法...
我可能是全世界唯一一个用了二次二分+二次枚举的人，
如果不是全场最慢我女装。
对于一个\text{X}，我们可以在O(\text{log}n)的时间复杂度内用二分算出小\text{Z}可以取到的最多的牌。
接下来有一个贪心：那就是小\text{Y}一定取他可以取到的最多的牌。(\forall \text{a}_i \geq1，故正确性显然)。这个值也可以用二分在O(\text{log}n) 的时间复杂度内求出来。
然后我们就有一个可以过前\text{4}个\text{subtasks}的做法，可以获得\text{70}分的高分：枚举小\text{Z}选了几张牌，然后二分求出小\text{Y}选了几张牌，两个值比较一下，如果小\text{Z}的分高于小\text{Y}的分，那\text{X}就是一个答案。
考虑满分做法：
通过观察得知，有一个神奇的性质：若\text{X}可行，设当前小\text{Z}取了\text{p}张牌，p一定大于\text{X}-\text{1}时小\text{Z}失败时取得最大牌数\text{q}。
为什么？因为在\text{X}-\text{1}时小\text{Z}都失败了，到了\text{X}时小\text{Y}取的牌只会单增不减，故一定失败。
加上这个优化就可以通过了。
代码： 

#include <bits/stdc++.h>

typedef long long ll;
const int N = 1e6 + 10;
int n, m, i, j, k, tot, p;
ll sum[N], ans[N];

int main() {
  scanf("%d", &n);
  for (int i = 1, a; i <= n; i++) scanf("%d", &a), sum[i] = sum[i - 1] + a;
  scanf("%d", &k), p = 1;
  for (int x = 1; x <= k; x++) {
    int l = 1, r = n, posA = 0;
    while (l <= r) {
      int mid = (l + r) >> 1; 
      ll s = sum[mid];
      if (s <= x) posA = mid, l = mid + 1;
      else r = mid - 1; 
    }
    bool flag = 1;
    for (int i = p; i <= posA; i++) {
      ll scoreA = sum[i];
      l = i + 1, r = n; int posB = 0;
      while (l <= r) {               
        int mid = (l + r) >> 1; 
        ll s = sum[mid] - sum[i];
        if (s <= x) {
          posB = mid, l = mid + 1;
          if (s >= scoreA) break;
        } else r = mid - 1; 
      }
      ll scoreB = posB == 0 ? 0 : sum[posB] - sum[i];
      if (scoreA > scoreB) { flag = 0; p = i; ans[++tot] = x; break; }
    }
    if (flag) p = posA;
  }
  printf("%d\n", tot);
  for (int i = 1; i <= tot; i++) printf("%d ", ans[i]);
  return 0;   
}