题目描述
一天，小 DD 决定买一些糖果。他决定在两家不同的商店中买糖果，来体验更多的口味。
在每家商店中都有 nn 颗糖果，每颗糖果都有一个权值：愉悦度，代表小 DD 觉得这种糖果有多好吃。其中，第一家商店中的第 ii 颗糖果的愉悦度为 AiAi，而第二家商店中的第 ii 颗糖果的愉悦度为 BiBi。
在每家商店买的糖果会被打包到一个袋子中（可以在一家商店什么都不买，此时认为这家商店的袋子为空）。小 DD 回家后，因为这两个袋子外观是一样的，所以他会从两个袋子中随机选择一个.，然后吃光里面的糖果。小 DD 定义一种买糖果的方案的愉悦度为：吃到的糖果的愉悦度之和的最小可能值。
购买每颗糖果的花费均为 WW，小 DD 想要最大化：买糖果的愉悦度与买糖果的花费之差（xx 与 yy 的差即为 x−yx−y），请你帮他求出这个最大值。
输入格式
第一行两个空格隔开的整数 n,Wn,W，表示每家商店中的糖果数目以及每颗糖果的花费。
第二行 nn 个空格隔开的整数 A1,A2,⋯,AnA1,A2,⋯,An，表示第一家商店中的糖果的愉悦度。
第三行 nn 个空格隔开的整数 B1,B2,⋯,BnB1,B2,⋯,Bn，表示第二家商店中的糖果的愉悦度。
保证输入的 {A}{A} 和 {B}{B} 均按照从小到大的顺序排列。
输出格式
输出一行一个整数，表示这个差值的最大值。
样例输入 1
4 10 12 14 16 19 14 15 20 37
样例输出 1
5
样例解释 1
最优方案为购买第一家商店中，愉悦度为 1616 和 1919 的两颗糖果，以及第二家商店中愉悦度为 3737 的糖果。
如果选择第一家商店的袋子，那么愉悦度之和为 3535；如果选择第二家商店的袋子，那么愉悦度之和为 3737；因此这种购买方案的愉悦度为 min{35,37}=35min{35,37}=35。
购买三颗糖果的代价为 3×10=303×10=30，所以差值为 35−30=535−30=5。
可以证明不存在更优的方案，所以答案为 55。
样例输入 2 & 3 & 4 & 5
见下发文件 ex_candy2.in/out，ex_candy3.in/out，ex_candy4.in/out 以及 ex_candy5.in/out。
数据规模与约定
本题共 2020 个测试数据，每个测试数据 55 分。
对于前 15%15% 的测试数据，n≤5n≤5；
对于另 15%15% 的测试数据，n≤10n≤10；
对于另 15%15% 的测试数据，n≤50n≤50；
对于另 15%15% 的测试数据，n≤200n≤200；
对于另 15%15% 的测试数据，n≤1000n≤1000；
对于另 15%15% 的测试数据，n≤5000n≤5000；
对于 100%100% 的测试数据，1≤n≤1051≤n≤105，1≤Ai,Bi,W≤1061≤Ai,Bi,W≤106。对于任意 1≤i<n1≤i<n，有 Ai≤Ai+1Ai≤Ai+1 且 Bi≤Bi+1Bi≤Bi+1。
时间限制：2s2s
空间限制：512MB
做法：ans=max(min(q[i],p[i]),w*(i+j)),q，p分别表示a，b从大到小时的前缀和，我们可以枚举其中一个，然后二分另一个。
1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #define N 100107 5 #define LL long long 6 #define rep(i,a,b) for(int i=a;i<=b;i++) 7 using namespace std; 8 int n,w,a[N],b[N]; 9 LL ans,qa[N],qb[N]; 10 11 inline int read(){ 12 int s=0; 13 char ch=getchar(); 14 for(;ch<'0'||ch>'9';ch=getchar()); 15 for(;ch>='0'&&ch<='9';s=s*10+ch-'0',ch=getchar()); 16 return s; 17 } 18 19 inline LL max(LL a,LL b){ 20 return a>b?a:b; 21 } 22 23 inline LL min(LL a,LL b){ 24 return a<b?a:b; 25 } 26 27 void Init(){ 28 n=read();w=read(); 29 rep(i,1,n) a[i]=read(); 30 rep(i,1,n) b[i]=read(); 31 rep(i,1,n) qa[i]=qa[i-1]+a[n-i+1],qb[i]=qb[i-1]+b[n-i+1]; 32 } 33 34 void Work(){ 35 rep(i,1,n){ 36 int l=1,r=n; 37 while(l<r){ 38 int mid=(l+r)>>1; 39 if (qb[mid]>=qa[i]) r=mid; 40 else l=mid+1; 41 } 42 ans=max(min(qa[i],qb[l])-w*(i+l),ans); 43 } 44 rep(i,1,n){ 45 int l=1,r=n; 46 while(l<r){ 47 int mid=(l+r)>>1; 48 if (qa[mid]>=qb[i]) r=mid; 49 else l=mid+1; 50 } 51 ans=max(min(qb[i],qa[l])-w*(i+l),ans); 52 } 53 printf("%lld",ans); 54 } 55 56 int main(){ 57 Init(); 58 Work(); 59 }