<span>Berry Jam （前缀和）cf教育场</span>
距离上一篇博客又2个月了 寻思着该除除草了
教育场是真的好难 可能是因为我还是只菜鸡 哭唧唧
先说下题意：有2*n罐果酱，草莓和蓝莓，梯子在中间从梯子那开始往两边吃（可以一会左一会右），问最少吃多少果酱可以使两种酱剩下的数量相等。
一开始没写出来，看了大佬的做法才会的。（因为下午刚考完拉链法冲突处理脑海里都是他ing，然后发现想复杂了.....）
题解：先将为2的改成-1。梯子右边从最右边开始求前缀和（前边所有果酱中两种果酱的差），记录前缀和的下标在数组c中（这个地方可能会有前缀和是一样的，那当然是让他越靠左越好了，这样没被吃的就越多了，所以从右边开始求前缀和），因为可能会有负数，所以前缀和加上100000存储。梯子左边从左求前缀和sum，然后右边界r--，比较求出n-r+c[-sum+100000]。也就是让左边少多少个那种酱，右边就得多多少个。
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 const int INF=0x3f3f3f; 5 const int maxn=100100; 6 int a[maxn],b[maxn],c[maxn*2],d[maxn]; 7 8 int main() 9 { 10 int t; 11 scanf("%d",&t); 12 while(t--){ 13 int n; 14 scanf("%d",&n); 15 for(int i=0;i<n;i++){ 16 scanf("%d",&a[i]); 17 if(a[i]!=1) a[i]=-1; 18 } 19 for(int i=0;i<n;i++){ 20 scanf("%d",&b[i]); 21 if(b[i]!=1) b[i]=-1; 22 } 23 for(int i=0;i<200100;i++) 24 c[i]=INF; 25 c[100000]=n; 26 d[n]=0; 27 for(int i=n-1;i>=0;i--) 28 d[i]=d[i+1]+b[i],c[d[i]+100000]=i; 29 int sum=0; 30 int ans=INF; 31 for(int i=0;i<n;i++) 32 sum+=a[i]; 33 ans=min(ans,c[-sum+100000]); 34 for(int i=n-1;i>=0;i--){ 35 sum-=a[i]; 36 ans=min(ans,n-i+c[-sum+100000]); 37 } 38 printf("%d\n",ans); 39 } 40 return 0; 41 }
途虎公司福利 103人发布
查看8道真题和解析