CF1278C

题目大意为给你一个2xN的数列问你从中间开始向左边或者向右边每次移动一个单位吃果酱,最少移动多少次可以吃的使得1号果酱的个数等于2号果酱的个数
首先记录最初的果酱的差值1-2为dif,然后我们发现如果往左边吃一号果酱,那么dif++,吃二号果酱dif–往右边同理。那么我们可以得到最终dif-difl-difr=0也就是说原来的差值减去左边贡献的差值减去右边贡献的差值最后结果为0.这样我们记录一下左边产生的差值在右边遍历寻找左边是否会有dif-difr的然后更新答案。最后注意一下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
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;
map<int,int> mk;
int a[200005];
int main()
{
int t;
cin>>t;
while(t--)
{
int n,s1=0,s2=0,cur=0,s;
cin>>n;
mk.clear();
for(int i=1;i<=2*n;i++)
cin>>a[i],s1+=(a[i]==1),s2+=(a[i]==2);
s=s1-s2;
mk[0]=0;
for(int i=n;i;i--)
{
if(a[i]==1) cur++;
else cur--;
if(!mk.count(cur))
mk[cur]=n-i+1;
}
cur=0;
int ans=2*n;
for(int i=n+1;i<=2*n;i++)
{
if(a[i]==1) cur++;
else cur--;
if(mk.count(s-cur))
ans=min(ans,i-n+mk[s-cur]);
}
if(mk.count(s))
ans=min(ans,mk[s]);
cout<<ans<<"\n";
}
}
就算是一分钱,也是对作者极大的支持
------ 本文结束 ------

版权声明

Baccano by baccano is licensed under a Creative Commons BY-NC-ND 4.0 International License.
baccano创作并维护的Baccano博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证
本文首发于baccano 博客( http://baccano.fun ),版权所有,侵权必究。

小游戏

---小游戏:要不要来选择一下自己可能的老婆?---

简易发声器

---简易的七键钢琴插件---

可以使用鼠标点击琴键也可以使用主键盘1-7或者小键盘的1-7来操作

那么现在开始吧

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
0%