codeforces-Ed78-C

codeforces-Ed78-C

七月 08, 2020

C - Berry Jam

题意
n个jam 梯子 n个jam
一共2*n个jam 1代表草莓酱 2代表蓝莓酱

一个人从中间向两侧中任意一侧取第一个未吃过的酱吃掉
问最少吃几罐能让剩下的草莓酱和蓝莓酱数量相等

发现吃的区间一定连续

可以利用前缀预处理和倒序遍历
前缀预1到n处理记录前i个草莓酱和蓝莓酱差值cnt
对于最后一次出现的差值cnt 记录/last[cnt]=i/ 它的位置
然后倒序遍历2n到n 对于右侧某位置i 草莓酱和蓝莓酱的差值为cnt
那么对应的左边前i个需要有差值-cnt 才能使得两端两者的数量相同

蓝莓酱比草莓酱多 cnt个 （位置last[-cnt]） ……需要吃掉…… 蓝莓酱比草莓酱少cnt个 （位置i）
因为cnt会出现负数可以用map来存前缀预处理的结果

其次注意last[0]=0 左边第0个位置 两者差值为0
倒序遍历时可能不会出现cnt=0的情况需要提前处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int data[(int)2e5+5];
map<int,int> last;
int main(){
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        int cnt=0;
        last.clear();last[0]=0;
        for(int i=1;i<=2*n;i++){
            cin>>data[i];
            if(data[i]==1)cnt++;
            else cnt--;
            if(i<=n)last[cnt]=i;
        }
        cnt=0;int ans=min(2*n,2*n-last[cnt]);
        for(int i=2*n;i>n;i--){
            if(data[i]==1)cnt--;
            else cnt++;
            ///cout<<cnt<<" "<<last[cnt]<<" "<<i<<endl;
            if(last.count(cnt))ans=min(ans,i-1-last[cnt]);
        }
        cout<<ans<<endl;
    }
}