题目链接：见这里 题意：每个队名有两种选择,然后第一个选择队名相同的那些队只能选第二种，让你安排队名，使得最后每个队名都不一样。 分析： 首先全都选成第一种队名，然后第一种队名相同的队,它们只能全都变成选第二种队名的了，这个时候如果第一种队名相同的那些队里面,变成第二种队名后有重复的,直接输出无解，这个时候先不管第一种队名，之后再处理第一种队名，看看第一种队名有没有和第二种队名重的，如果有重的话就让他变到第二种队名，以此法贪心就好。代码能力太差，debug好久好久。
#include <bits/stdc++.h>using namespace std;const int maxn = 1100;int n;string s1, s2;string name1[maxn], name2[maxn]; //A, Bint pos[maxn]; //记录哪些需要变成第2种map <string, vector <int> > mp1, mp2;map <string, int> m1, m2;map <string, bool> vis; //标记哪些第1种名字被处理int main(){ //input cin >> n; for(int i = 1; i <= n; i++){ cin >> s1 >> s2; name1[i] = "", name2[i] = ""; name1[i] += s1.substr(0, 3); name2[i] += s1.substr(0, 2); name2[i] += s2[0]; mp1[name1[i]].push_back(i); m1[name1[i]]++; } // for(int i = 1; i <= n; i++){ if(!vis[name1[i]]){ int len = mp1[name1[i]].size(); if(len > 1){ for(int j = 0; j <= len - 1; j++){ m1[name1[i]]--; int id = mp1[name1[i]][j]; pos[id] = 1; m2[name2[id]]++; if(m2[name2[id]] > 1){ puts("NO"); return 0; } } } vis[name1[i]] = 1; } } // while(1){ bool flag = 1; for(int i = 1; i <= n; i++){ if(pos[i] == 0){ if(m2[name1[i]]){ flag = 0; if(m2[name2[i]]){ puts("NO"); return 0; } else{ pos[i] = 1; m2[name2[i]] = 1; } } } } if(flag) break; } puts("YES"); for(int i = 1; i <= n; i++){ if(pos[i] == 0) cout << name1[i] << endl; else cout << name2[i] << endl; } return 0;}新闻热点
疑难解答
