[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\) 为两所有数的总和。题目要求：
我们将三边都乘二减去 \(S\)，变成：
设 \(x\) 为 \(S-(L+R)\)，整体加上 \(x\) 之后变成：
转化一下后变成：
这个时候，我们将题意转化完成了：
给定整数 \(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)\) 这样的是小数减去大数，结果是负数，我们将它称为下界，即绝对值里面的最小值（负数），我们将它相反一下得到上界，即一个临项差分形式：
但是当 \(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;
}