A. Kids Seating
从4*n-2开始，每次输出减2。
发现满足条件，不互质也不能相互整除
B. Saving the City
引爆花费a，安装花费b
可知要引爆必定花费一个a，ans+=a
对于两段1区间中间隔着的0，既可以用安装一个个1花费 cnt*b 也可以花费a引爆
那么每次记录下来，然后比较 ans+=min（cnt*b，a）就行
代码不贴了，开始想复杂了，导致过的很慢，码风也很丑陋
C. The Delivery Dilemma
给定两个序列，表示 取走某一个物品的a值和b值。
我们要取每一个物品，通过a值取的贡献取大，通过b值取的贡献累加，最后两者再取大。
思路就很明显了，按a排序，每次取i，那么i之前的物品都可以通过a值取，也就是没有花费。
i之后的物品，累加b值，然后两者取大，就是该做法的最后答案。
ll ans,sum[200007]; struct nod{ ll a,b; }node[200007]; int cmp(nod x,nod y){ return x.a<y.a; } int t,n; int main(){ scanf("%d",&t); while(t--){ scanf("%d",&n); ans=inf; for(int i=1;i<=n;++i) scanf("%lld",&node[i].a); for(int i=1;i<=n;++i) scanf("%lld",&node[i].b); sort(node+1,node+1+n,cmp); for(int i=1;i<=n;++i) sum[i]=sum[i-1]+node[i].b; for(int i=1;i<=n;++i){ if(node[i].a>sum[n]-sum[i]) ans=min(ans,node[i].a); else ans=min(ans,sum[n]-sum[i]); } ans=min(ans,node[n].a); ans=min(ans,sum[n]); printf("%lld\n",ans); } return 0; }
思路二：二分
不对a进行排序，直接对答案进行二分，判断当前的答案是否能满足条件。
如果物品i的a值大于我的答案x，那么sum累加b值。
如果最后b值反而大于x，那么不成立。
成立的话说明，x还能继续缩小，让更多的物品去贡献b值到sum。
以下是队友优秀的码风
ll a[N],b[N],n; int check(ll x){ ll ans=0; FR(i,1,n) if(a[i]>x)ans+=b[i]; if(ans>x)return 0; return 1; } int main(){ int t; string s; scanf("%d",&t); while(t--){ scanf("%lld",&n); ll sum=0,maxn=0; FR(i,1,n){ scanf("%lld",&a[i]); maxn=max(maxn,a[i]); } FR(i,1,n){ scanf("%lld",&b[i]); sum+=b[i]; } ll l=1,r=max(maxn,sum); ll mid; while(l!=r){ mid=(l+r)/2; if(check(mid))r=mid; else l=mid+1; } printf("%lld\n",l); } return 0; }
D. Extreme Subtraction
两种操作法，一种是从头到i都减1，第二种事从尾到i都减1
那么先差分，我们的目标就是差分数组都为0
操作1使得【1，i+1】 操作2使得【i，n+1】
-1 +1 -1 +1
很明显了，差分数组中间的任意值都能被操作12改为0，我们并不在意n+1位的差分是多少
那么a1就成了限制我们操作的条件，对于差分数组中的负值，我们只能通过操作1操作。
如果一个题看起来像差分，写起来也像，那他就是差分
a[0]=0; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); c[i]=a[i]-a[i-1]; } int res=0; for(int i=2;i<=n;i++) if(c[i]<0) res=res+(-1)*c[i]; if(res<=a[1]) printf("YES\n"); else printf("NO\n");