Berry Jam （前缀和）cf教育场

距离上一篇博客又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 }

巴特西

Berry Jam （前缀和）cf教育场

最新文章

热门文章