问题描述
一天，小 D 决定买一些糖果。他决定在两家不同的商店中买糖果，来体验更多的口味。
在每家商店中都有 n 颗糖果，每颗糖果都有一个权值：愉悦度，代表小 D 觉得这种糖果有多好吃。其中，第一家商店中的第 i 颗糖果的愉悦度为 Ai，而第二家商店中的第 i 颗糖果的愉悦度为 Bi。
在每家商店买的糖果会被打包到一个袋子中（可以在一家商店什么都不买，此时认为这家商店的袋子为空）。小 D 回家后，因为这两个袋子外观是一样的，所以他会从两个袋子中随机选择一个.，然后吃光里面的糖果。小 D 定义一种买糖果的方案的愉悦度为：吃到的糖果的愉悦度之和的最小可能值。
购买每颗糖果的花费均为 W，小 D 想要最大化：买糖果的愉悦度与买糖果的花费之差（x 与 y 的差即为 x−y），请你帮他求出这个最大值。
输入格式
第一行两个空格隔开的整数 n,W，表示每家商店中的糖果数目以及每颗糖果的花费。
第二行 n 个空格隔开的整数 A1,A2,⋯,An，表示第一家商店中的糖果的愉悦度。
第三行 n 个空格隔开的整数 B1,B2,⋯,Bn，表示第二家商店中的糖果的愉悦度。
保证输入的 {A} 和 {B} 均按照从小到大的顺序排列。
输出格式
输出一行一个整数，表示这个差值的最大值。
样例输入
4 10
12 14 16 19
14 15 20 37
样例输出
5
数据范围
1≤n≤105，1≤Ai,Bi,W≤106。对于任意 1≤i<n，有 Ai≤Ai+1 且 Bi≤Bi+1。
解析
考虑贪心，实际上在每个商店中选择愉悦值尽量大的糖果一定更优。我们设在第一个商店中从大到小选择了(i)个，第二个商店中从大到小选择了(j)个。我们将这两个指针不断向后移动。当一个糖果店的糖果愉悦值之和第一次大于另一家店时，我们移动另一家店的指针，每次统计答案，直到这家店的总和大于另一家店。可以理性证明，此时的答案一定不会更差。
代码
#include <iostream>
#include <cstdio>
#define N 100002
using namespace std;
int n,w,i,j,a[N],b[N];
long long suma,sumb,cnt,ans;
int read()
{
char c=getchar();
int w=0;
while(c<'0'||c>'9') c=getchar();
while(c<='9'&&c>='0'){
w=w*10+c-'0';
c=getchar();
}
return w;
}
int main()
{
n=read();w=read();
for(i=1;i<=n;i++) a[i]=read();
for(i=1;i<=n;i++) b[i]=read();
i=j=n;
while(i>0||j>0){
if(suma<sumb){
if(i==0) break;
while(i>=1&&suma<=sumb){
suma+=a[i],cnt++;
ans=max(ans,min(suma,sumb)-cnt*w);
i--;
}
}
else{
if(j==0) break;
while(j>=1&&sumb<=suma){
sumb+=b[j],cnt++;
ans=max(ans,min(suma,sumb)-cnt*w);
j--;
}
}
}
printf("%lld
",ans);
return 0;
}