（easy version）：
題目鏈接：http://codeforces.com/contest/1296/problem/E1
題目一句話就是說，兩種顏色不同的字符可以相互換位，
問，對這字串用最多兩種顏色染色，然后經過有限次換位
可以變成字典序排序的順序，
思路：一個字符需不需要換位，應該是參照最后的字典序的順序，
那么，我們應該給字串排序，再去思考問題，
我們知道，如果str[now_i]的位置和排序后的位置不一樣，那就是需要換位，
我們還知道，如果str[now_i]的當前位置如果小于等于排序后的位置，
說明str[now_i]會往后移動，之前應該是會多出（>=0）個字符，那么我們不妨
讓str[now_i]不主動移動（標記‘0’），讓str[now_x]當前位置大于排序后位置的去向前主動移動（也必須向前移動）（標記‘1’），
那么經過一些str[now_x]向前移動，str[now_i]會被動的回到排序后的位置，從而達到"YES"，
那什么情況是“NO”？
如果我們標記的'1'字符組成的字串出現了"ba"，”bca”，就是說不滿足非遞減性質，
那么"ba"，a是'1'，b也是'1'，就是說，a不可能到b前面，那也就是“NO”了，舉個樣例：
7
abcdedc
0000011
撇開這個樣例不管，如果出現了"ba"，如果把要b換成'0'，那么之前本該屬于b位置的需要變成'1'，
使得可以和b轉位，但是被換成'1'的那個字符又導致'a'不能回到a本該屬于的位置，所以這個情況是''NO"就證明成立了，也間接證明了"YES"情況的正確性，所以方法猜想正確，之后的做法就只需要維護這個方法就行，
時間復雜度可以是O（n）
1 #include <iostream> 2 #include <algorithm> 3 #include <string> 4 #include <queue> 5 #include <cstdio> 6 using namespace std; 7 8 struct Info{ 9 queue<int > index; 10 void pb(int x){ index.push(x); } 11 int loc(){ int x = index.front(); index.pop(); return x; } 12 }info[30];//存盤不同字符出現的位置 13 14 int main(){ 15 16 string str; 17 int a[500]; 18 int col[500];//顏色 19 int n; 20 cin >> n >> str; 21 for(int i = 0; i < n;++i) a[i] = str[i]-'a';//字符轉化為數字 22 sort(a,a+n);//排序 23 for(int i = 0; i < n; ++i) info[a[i]].pb(i);//把該字符出現的位置記錄 24 char error[10] = "aa";//error[0]存盤的是不需要主動移動的字符最大是哪個 25 //error[1]存盤的是需要主動移動的字符最大的是哪個 26 for(int now = 0; now < n; ++now){//now表示當前位置 27 int after = info[str[now]-'a'].loc();//取一個該字符排序后的位置 28 if(now <= after){//當前位置小于等于排序后的位置，這里有個特殊情況， 29 //abcdedc① 30 //abccdde 31 //可以看出第二個d雖然和排序后的位置一樣，但是他需要換位 32 if(str[now] >= error[0]){ 33 error[0] = str[now]; 34 col[now] = 0; 35 }else{ 36 col[now] = 1; 37 if(str[now] > error[1]) error[1] = str[now];//①的情況出現需要改變error[1]的字符 38 } 39 } 40 else{ 41 if(str[now] >= error[1]){ 42 col[now] = 1; 43 error[1] = str[now]; 44 }else{ 45 error[1] = '!'; break; 46 } 47 } 48 } 49 if(error[0] == '!' || error[1] == '!') cout << "NO\n"; 50 else{ 51 cout << "YES\n"; 52 for(int i = 0; i < n; ++i) cout << col[i]; 53 cout << endl; 54 } 55 56 return 0; 57 }
(hard version)：
題目鏈接：http://codeforces.com/contest/1296/problem/E2
題目：E1說明了只能用兩種顏色去染色，現在是最少用幾種顏色去染色，可以完成字典序排序，
思路：再次思考E1的證明情況，如果該字符需要染成'1'，那么它們組成的字串是“單調非遞減”的，
而'0'組成的字串也是“單調非遞減”的，于是，我們想到，可以把這個題目抽象成一些數字組成一個序列，
問你該序列最少可以分成幾個滿足性質“非單調遞減”的集合，也就是幾種顏色了，
那么E2題目就變得簡單了，E1也可以不那么復雜的寫了，
最多26個字符，也就是最多26個集合，那么 時間復雜度是O（26*n），
這里有個細節，我們需要充分利用字符之間的間隔，舉個例子：
abacd...
先分成兩個集合 ：ab ac，應該把d放在"ac"的后面，這樣才能充分能利用字符之間的間隔，滿足最少顏色，
1 #include <iostream> 2 #include <vector> 3 #include <string> 4 #include <algorithm> 5 using namespace std; 6 7 const int N = (int)2e5+100; 8 struct node{ 9 int index; 10 char ch; 11 }; 12 int col = 0;//集合數 13 string str;//每個集合最后的字符 14 int ans[N]; 15 16 int main(){ 17 18 ios::sync_with_stdio(false); 19 cin.tie(0); cout.tie(0); 20 int n; 21 char ch,max_ch,which_col,len,tmp_ch,now_ch; 22 cin >> n; 23 for(int i = 0; i < n; ++i){ 24 cin >> ch; 25 which_col = -1;//選哪種顏色 26 tmp_ch = 'A'; 27 for(int j = 0; j < col; ++j){ 28 now_ch = str[j]; 29 //選col個集合中最后字符小于等于ch且最接近ch的 30 if(now_ch <= ch){ 31 if(now_ch > tmp_ch){ 32 tmp_ch = now_ch; 33 which_col = j; 34 } 35 } 36 } 37 if(which_col != -1){ 38 str[which_col] = ch; 39 ans[i] = which_col+1; 40 } 41 else{ 42 //需要新加一種顏色 43 str += ch; 44 ++col; 45 ans[i] = col; 46 } 47 } 48 49 cout << col << endl; 50 cout << ans[0]; 51 for(int i = 1; i < n; ++i) cout << ' ' << ans[i]; 52 cout << endl; 53 54 55 return 0; 56 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/91927.html
標籤：其他
下一篇：什么是鏈表？