Discarding Game

\[Time Limit: 3000 ms\quad Memory Limit: 524288 kB\]

题意

一个人和一个电脑在玩游戏,游戏规则是

  1. 游戏有 \(n\) 轮,每一轮人获得 \(a_i\),电脑获得 \(b_i\)
  2. 当一方的分数超过 \(k\),那一方就获胜,如果两方都超过了 \(k\),无人获胜。
  3. 当有人的分数到达 \(k\) 以后,游戏提前结束。如果游戏结束都没人分数超过 \(k\),则双方平局,无人获胜。
  4. 玩家有一个 \(RESET\) 按钮,假设人的分数为 \(x\),电脑分数为 \(y\),按下之后,\(x' = max(0, x-y)\)\(y' = max(0, y-x)\) 并且 \(x'、y'\) 重新成为人和电脑的分数。

现在玩家想要知道,如果他可以获胜,他应该在那些轮按下 \(RESET\),输出要按的次数最少的方案。

思路

首先我们可以发现:

  1. \(RESET\) 按钮其实就是将人和电脑的分数减去其中的较小值。
  2. 在不考虑 \(k\) 的限制下,有 \(a、b、c\) 三轮游戏,在 \(b\) 按下 \(RESET\) 后在 \(c\) 再按下 \(RESET\) 的效果和直接在 \(c\) 按下 \(RESET\) 的效果是一样的。
  3. 在不考虑 \(k\) 的限制下,按下的 \(m\)\(RESET\),都可以看成到倒数第二轮按下一次,在最后一轮在按下一次。

\(sa\)\(a\) 的前缀和,\(sb\)\(b\) 的前缀和,\(w\)\(sa\)\(sb\) 的较小值。
如果在第 \(i\) 轮可以获胜,并且上一次按在第 \(L\) 轮,那么一定要满足以下条件:
\[\begin{cases}sa[i]-w[L] < k\\sb[i]-w[L] >= k\end{cases}\\\begin{cases}sa[i]-k < w[L] \\sb[i]-k >= w[L]\end{cases}\]
所以对于每一轮游戏,只要找到是否有满足的 \(L\),就可以确定是否有可能获胜了。
由于 \(sa、sb、w\) 都是递增的,所以 \(i\) 增加时, \(L\) 是单调的,那么找 \(L\) 的过程就是线性的。
那么只要找到最小的 \(i\) 和对应的 \(L\) ,然后当人在前 \(L\) 轮的分数不超过 \(k\),并且在 \(L\) 轮按一次 \(RESET\),就可以保证在第 \(i\) 轮获胜。
由于这样找到的 \(i\) 是最小的并且前 \(i-1\) 轮都无法获胜,那么这样操作的次数一定是最少的。

/***************************************************************
    > File Name     : G.cpp
    > Author        : Jiaaaaaaaqi
    > Created Time  : Sun 03 Nov 2019 10:37:18 PM CST
 ***************************************************************/

#include <map>
#include <set>
#include <list>
#include <ctime>
#include <cmath>
#include <stack>
#include <queue>
#include <cfloat>
#include <string>
#include <vector>
#include <cstdio>
#include <bitset>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#define  lowbit(x)  x & (-x)
#define  mes(a, b)  memset(a, b, sizeof a)
#define  fi         first
#define  se         second
#define  pb         push_back
#define  pii        pair<int, int>

typedef unsigned long long int ull;
typedef long long int ll;
const int    maxn = 2e5 + 10;
const int    maxm = 1e5 + 10;
const ll     mod  = 1e9 + 7;
const ll     INF  = 1e18 + 100;
const int    inf  = 0x3f3f3f3f;
const double pi   = acos(-1.0);
const double eps  = 1e-8;
using namespace std;

int n, m;
int cas, tol, T;

ll a[maxn], b[maxn], k;
ll sa[maxn], sb[maxn], w[maxn];
vector<int> vv;

int findwin() {
    int L = 0;
    int ans = -1;
    for(int i=1; i<=n; i++) {
        while(L<=n && sa[i]-k >= w[L])  L++;
        if(sa[i]-k < w[L] && w[L] <= sb[i]-k) {
            ans = i;
            break;
        }
    }
    if(!L || ans == -1) return ans;
    {
        ll A, B;
        A = B = 0;
        for(int i=1; i<L; i++) {
            A += a[i], B += b[i];
            if(A+a[i+1] >= k) {
                vv.pb(i);
                ll x = min(A, B);
                A -= x, B -= x;
                if(A+a[i+1]>=k) return -1;
            }
        }
        vv.pb(L);
    }
    return ans;
}

int main() {
    // freopen("in", "r", stdin);
    scanf("%d", &T);
    while(T--) {
        vv.clear();
        scanf("%d%lld", &n, &k);
        sa[0] = sb[0] = w[0] = 0;
        for(int i=1; i<=n; i++) {
            scanf("%lld", &a[i]);
            sa[i] = sa[i-1]+a[i];
        }
        for(int i=1; i<=n; i++) {
            scanf("%lld", &b[i]);
            sb[i] = sb[i-1]+b[i];
            w[i] = min(sa[i], sb[i]);
        }
        // printf("sa: "); for(int i=1; i<=n; i++) printf("%lld%c", sa[i], i==n?'\n':' ');
        // printf("sb: "); for(int i=1; i<=n; i++) printf("%lld%c", sb[i], i==n?'\n':' ');
        // printf("w : "); for(int i=1; i<=n; i++) printf("%lld%c", w[i], i==n?'\n':' ');
        int pos = findwin();
        if(pos == -1) {
            printf("-1\n");
        } else {
            if(vv.size() == 0) {
                printf("0\n\n");
            } else {
                sort(vv.begin(), vv.end());
                printf("%d\n", vv.size());
                for(int i=0; i<vv.size(); i++) {
                    printf("%d%c", vv[i], i==vv.size()-1?'\n':' ');
                }
            }
        }
    }
    return 0;
}
12-21 12:40