首页 > 代码库 > 项链分赃

项链分赃

2024-11-02 08:39:39   208人阅读

Time Limit: 4 Sec  Memory Limit: 128 MB
Submit: 184  Solved: 116
[Submit][Status][Discuss]

Description

有一串长度为n的项链，上面有红绿蓝三种颜色的珠子，每种颜色的珠子数目都是偶数，现在要你把它切几刀分成
若干段，把其中一些段分给海盗1，剩余的段分给海盗2，要求两个海盗分得的每种颜色的珠子数量都相同，请输出
最少需要切多少刀。

Input

第一行一个整数n，表示项链的长度。
第二行n个0~2的整数，分别表示红绿蓝三种颜色。

Output

一行一个整数，为最少切多少刀。

Sample Input

6
0 2 2 1 0 1

Sample Output

2
样例解释：切两刀，分成{0,2},{2,1,0},{1}三份，第二份给海盗1，剩下给海盗2即可。

HINT

n<=100000

Source

By Monster_Yi

思路

B站出题人系列；

因为某一个奇妙的 http://www.bilibili.com/video/av9885078/ ；

得证，n种宝石最多切n刀；

所以，ans∈{1,2,3};

然后就看看切几刀了；

代码实现

 1 #include<set> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<algorithm> 5 using namespace std; 6 const int maxn=1e5+10; 7 int n,a[maxn],b[3],c[3]; 8 set<pair<int,pair<int,int> > > v; 9 int main(){10     scanf("%d",&n);11     for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[a[i]]++;12     b[0]>>=1,b[1]>>=1,b[2]>>=1;13     for(int i=1;i<=n;i++){14         c[a[i]]++;15         if(b[0]==c[0]&&b[1]==c[1]&&b[2]==c[2]) return printf("1\n"),0;16     }17     c[0]=c[1]=c[2]=0;18     for(int i=1;i<=n;i++){19         c[a[i]]++;20         if(v.count(make_pair(c[0]-b[0],make_pair(c[1]-b[1],c[2]-b[2])))) return printf("2\n"),0;21         v.insert(make_pair(c[0],make_pair(c[1],c[2])));22     }23     return printf("3\n"),0;24 }

 

项链分赃


联系
我们