[AGC056D] Subset Sum Game

佚名 / 2023-08-22 / 原文

[AGC056D] Subset Sum Game

一、题目大意：

一块黑板上写着 \(n\) 个整数。第 \(i\) 个整数记作 \(a_i\)。保证 \(n\) 是偶数。此外，给定 \(L,R\)。

Alice 和 Bob 在玩一个游戏。他们轮流操作，Alice 先手。在每一轮中，玩家需要选择一个写在黑板上的数，并擦掉它。

游戏会在 \(n\) 轮后结束。令 \(s\) 为 Alice 擦掉的数之和。若 \(L \le s \le R\)，则 Alice 胜利，反之 Bob 胜利。你需要输出当两方都采取最优策略情况下的赢家。

二、题意转化：

设 \(S_a\) 为 Alice 擦掉数的总和，\(S_b\) 为 Bob 的擦掉数的总和，设 \(S\) 为两所有数的总和。题目要求：

\[L\le S_a\le R \]

我们将三边都乘二减去 \(S\)，变成：

\[2L-S\le 2S_a-S\le 2R-S \]

设 \(x\) 为 \(S-(L+R)\)，整体加上 \(x\) 之后变成：

\[L-R\le x+S_a-S_b\le R-L \]

转化一下后变成：

\[|x+S_a-S_b|\le R-L \]

这个时候，我们将题意转化完成了：

给定整数 \(x\)，Alice 操作是选择一个数 \(a_i\) 使 \(x=x+a_i\)，Bob操作是选择一个数 \(a_i\)，使 \(x=x-a_i\)，Alice 想使 \(x\) 尽量小，Bob 想使 \(x\) 尽量大，在最优策略下问谁能赢。

三、思路

Alice 想使 \(x\) 尽量小，又因为是 \(+S_a\)，所以选择绝对值小的数。

Bob 想使 \(x\) 尽量大，又因为是 \(-S_b\)，所以也选择绝对值小的数。

将 \(a\) 数组升序排列之后，当 \(x=0\) 时，我们发现按上面两行所说应该是

\[(a_1-a_2)+(a_3-a_4)+\dots+(a_{n-1}-a_n) \]

但是因为转化后的题意让你求的是绝对值大小，而 \((a_1-a_2)\) 这样的是小数减去大数，结果是负数，我们将它称为下界，即绝对值里面的最小值（负数），我们将它相反一下得到上界，即一个临项差分形式：

\[(a_2-a_1)+(a_4-a_3)+\dots+(a_{n}-a_{n+1}) \]

但是当 \(x\ne 0\) 时，我们如果这样想是错误的：单独算出临项差分后，在加个 \(x\)。因为临项差分是将 \(a\) 数组升序排列之后取的结果，如果你单独加 \(x\) 的话，那就是默认是 Alice 取的了，但是实际上 Bob 也能取，那么怎么判断是 Alice 取还是 Bob 取呢？

如果想要把 \(x\) 的贡献加进去，我们需要将某个 \(a_i\) 替换成 \(a_i+x\) 后升序排列，再用差分求出答案，将每个 \(a_i\) 都试过之后，得到的最小答案即为最终结果，判断一下是否满足
\(|x+S_a-S_b|\le R-L\) 就行了。

差分形式能是一个序列的最优策略，替换之后升序的序列用差分形式也是最优策略，而单独加 \(x\) 却不一定是。

因为我们计算临项差分插入元素，又循环枚举 \(a_i\)，所以时间复杂度 \(n^2\)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace Testify{
    inline int read(){
        int f(1),x(0);
        char ch=getchar();
        for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
        for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
        return f*x;
    }
    
    inline void Write(int x){
        if(x>9) Write(x/10);
        putchar(x%10+48);
    }
    inline void write(int x){
        if(x<0) putchar('-'),x=-x;
        Write(x);
        putchar('\n');
    }
}
using namespace Testify;
int n,l,r,Tempestissimo(LONG_LONG_MAX);
int x(0);
const int N=5005;
int a[N],b[N];
int cnt1,cnt2;
vector<int> q;
// priority_queue<int,vector<int>,greater<int>> q;
signed main(void){
    n=read(),l=read(),r=read();
    for(register int i=1;i<=n;i++){
        a[i]=read();
        x+=a[i];
    }
    x-=(l+r);
    sort(a+1,a+n+1);
    for(register int i=1;i<=n;i++){
        int cnt=0;
        q.clear();
        for(register int j=1;j<=n;j++){
            if(i==j) continue;
            q.push_back(a[j]);
        }
        int ans=0;
        q.insert(lower_bound(q.begin(),q.end(),a[i]+x),a[i]+x);
        bool flag=true;
        for(register int j=0;j<n;j+=2){
            ans+=(q[j+1]-q[j]);
        }
        Tempestissimo=min(Tempestissimo,ans);
    }
    if(abs(Tempestissimo)<=r-l){
        puts("Alice");
    }
    else{
        puts("Bob");
    }
    return 0;
}