題目鏈接：見這里 題意：每個隊名有兩種選擇,然后第一個選擇隊名相同的那些隊只能選第二種，讓你安排隊名，使得最后每個隊名都不一樣。 分析： 首先全都選成第一種隊名，然后第一種隊名相同的隊,它們只能全都變成選第二種隊名的了，這個時候如果第一種隊名相同的那些隊里面,變成第二種隊名后有重復的,直接輸出無解，這個時候先不管第一種隊名，之后再處理第一種隊名，看看第一種隊名有沒有和第二種隊名重的，如果有重的話就讓他變到第二種隊名，以此法貪心就好。代碼能力太差，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;}新聞熱點
疑難解答
