P11393 [JOI Open 2019] 汇款 / Remittance 题解
XYZyyds_3799
·
·
题解
模拟赛 T3（怎么大家都这样）。
赛时写挂了被捆绑测试阴了，赛后看题解发现我的思路怎么和大家都不一样 /ll。
怒调 1h 成功，写篇题解。
题意
有 N 座房子围成一圈，按逆时针方向用 1 \sim N 编号。初始第 i 座房子有 A_i 元，目标是达到 B_i 元。每座房子可以给它左边相邻的房子汇款，使得 A_i 减少 2x，B_i 增加 x，需判断是否存在合法操作达成目标。
思路
题解区全是贪心，来个二分思路。
以下称一座房子从它右边的房子得到的钱为收入（扣除手续费后），向左边的房子汇款的钱为支出（未扣除手续费）。
定义 C_i=A_i-B_i，in_i 为第 i 座房子的收入，out_i 为第 i 座房子的支出，那么有 C_i=out_i-in_i,out_i=2 \cdot in_{i+1}。
该方程组为线性递推 + 环形约束，若存在可行解则一定唯一。
考虑二分第 1 座房子的收入 x，即 in_1=x。
可以推出 out_n=2x 和 out_1=C_1+x \Rightarrow in_2=\frac{out_1}{2}。
由 in_2 继续向后推至 in_n=\frac{out_{n-1}}{2} 和理论 out'_n=C_n+in_n，此时判断理论 out_n 与之前计算出来的 out_n=2x 的大小关系：
::::info[单调性证明]{close}
令 \Delta(x)=out'_n-2x，证明 \Delta(x) 严格单调递减：
:::info[引理]{close}
- 引理：对任意 k \in [1,n]，存在常数 P_k 使得 in_k(x) = P_k+\frac{x}{2^{k-1}}。
数学归纳法证明：
基例 k=1：in_1(x)=x=0+\frac{x}{2^0}，即 P_1=0 成立。
设对 k=m 有 in_m(x)=P_m+\frac{x}{2^{m-1}}。
当 k=m+1 时有：
out_m(x)=C_m+in_m(x)=C_m+P_m+\frac{x}{2^{m-1}}
in_{m+1}(x)=\frac{out_m(x)}{2}=\frac{C_m+P_m}{2}+\frac{x}{2^m}
则令 P_{m+1}=\frac{C_m+P_m}{2}，满足形式，归纳成立。
:::
取 k=n，代入引理结论：
in_n(x)=P_n+\frac{x}{2^{n-1}}
out'_n(x)=C_n+in_n(x)=(C_n+P_n)+\frac{x}{2^{n-1}}
\Delta(x)=out'_n(x)-2x=\underbrace{(C_n+P_n)}_{\text{Const}}+x \cdot (\frac{1}{2^{n-1}}-2)
题目保证 $n \ge 2$，故 $2^{n-1} \ge 2$，$\Delta(x)$ 斜率满足：
$$
\frac{1}{2^{n-1}}-2 \le \frac{1}{2}-2 = -\frac{3}{2} < 0
$$
斜率恒负，故 $\Delta(x)$ 严格单调递减。
::::
写得比较丑陋 /kel。
## 代码实现
123 行【】代码，谨慎食用。
:::success[Code]{close}
```cpp
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const double eps=1e-10;//防止精度误差
int n,a[1000001],b[1000001],nowin[1000001],nowout[1000001];
double c[1000001],in[1000001],out[1000001];//注：代码中out数组存储的是负数支出值
__int128 sum=0;
bool cheek()//检验是否合法
{
for(int i=1;i<=n;i++)//初始化
{
nowin[i]=nowout[i]=0;
}
for(int i=1;i<=n;i++)
{
if(in[i]<0||out[i]>0||(in[i]!=0&&abs((int)in[i]-in[i])>eps)||(out[i]!=0&&abs((int)out[i]-out[i])>eps)||(int)out[i]%2!=0) return false;
}
bool can=false;
while(1)
{
can=false;//本轮能否继续操作
for(int i=1;i<=n;i++)
{
if(nowout[i]>out[i]&&a[i]+nowin[i]+nowout[i]>0)
{
int k=min((int)(nowout[i]-out[i]),a[i]+nowin[i]+nowout[i])/2*2;//只支出偶数
nowout[i]-=k;
nowin[i%n+1]+=k/2;
if(k!=0) can=true;
}
}
if(can==false) break;
}
for(int i=1;i<=n;i++)//再次遍历检验
{
if(a[i]+nowin[i]+nowout[i]!=b[i])
{
return false;
}
}
return true;
}
/*
check函数返回值：
{true,true}满足条件，有正整数解
{true,false}满足条件，无正整数解
{false,false}不满足条件，大了
{false,true}不满足条件，小了
*/
pair<bool,bool> check(int x)
{
in[1]=x;
out[1]=-c[1]-x;
out[n]=-2*x;
for(int i=2;i<n;i++)
{
in[i]=out[i-1]/-2.0;
out[i]=-c[i]-in[i];
}
in[n]=out[n-1]/-2.0;
double t=-c[n]-in[n];
if(t==out[n])
{
if(cheek()) return {true,true};
else return {true,false};
}
if(t<out[n]) return {false,true};
return {false,false};
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i]>>b[i];
c[i]=a[i]-b[i];
sum+=c[i];
}
//一些特判
if(sum<0)
{
cout<<"No\n";
return 0;
}
if(sum==0)
{
for(int i=1;i<=n;i++)
{
if(c[i]!=0)
{
cout<<"No\n";
return 0;
}
}
cout<<"Yes\n";
return 0;
}
long long l=0,r=2e9;//常数稍大
while(l<=r)
{
long long mid=(l+r)>>1;
auto p=check(mid);
if(p.first&&p.second)
{
cout<<"Yes\n";
return 0;
}
else if(p.first)
{
break;
}
else if(p.second)
{
l=mid+1;
}
else r=mid-1;
}
cout<<"No\n";
return 0;
}
```
:::