Description n个点，初始颜色c[i]，m次染色，每个给某个点涂上另一种颜色，问最少几次操作后所有点颜色相同 Input 第一行一整数n表示点数，之后n个整数c[i]表示每个点的颜色，之后一整数m表示染色数，最后m行每行两个整数a和b表示给a点染b颜色(1<=n<=1e5,1<=c[i]<=1e9,1<=m<=3e5,1<=a<=n,1<=b<=1e9) Output 输出最少操作数使得所有点同色，如果m次染色后所有点颜色还不全相同则输出-1 Sample Input 3 4 3 7 4 1 5 2 7 1 7 3 3 Sample Output 3 Solution 开个map存每种颜色的数量，每次染色就把原颜色数量减一，新颜色数量加一，如果第一个点的颜色的数量是n说明所有点同色 Code
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<queue> #include<map> #include<set> #include<ctime> using namespace std; typedef long long ll; #define INF 0x3f3f3f3f #define maxn 111111 int n,m,c[maxn],a[3*maxn][2]; map<int,int>M; int main() { while(~scanf("%d",&n)) { M.clear(); for(int i=1;i<=n;i++)scanf("%d",&c[i]),M[c[i]]++; scanf("%d",&m); for(int i=1;i<=m;i++)scanf("%d%d",&a[i][0],&a[i][1]); int gg=1; if(M[c[1]]==n) { printf("0\n"); continue; } for(int i=1;i<=m;i++) { M[c[a[i][0]]]--; c[a[i][0]]=a[i][1]; M[c[a[i][0]]]++; if(M[c[1]]==n) { printf("%d\n",i); gg=0; break; } } if(gg)printf("-1\n"); } return 0; }