題意：
給出了字符串s的內容，字符串t，u初始默認為空，允許做兩種操作：
1.把s字符串第一個字符轉移到t字符串最后。
2.把t字符串最后一個字符轉移到u字符串最后。
最后要求s、t字符串都為空，問u字符串字典序最小能是多少。

題解：
本題實質為一個棧混洗，s為初始棧，t為中間棧，u為結果棧。
我們考慮這樣的貪心策略：如果t棧為空，那么做s->t；
如果t棧不空：
對于t棧頂，如果s棧中不存在比它字典序更小的單詞，就做t->u
否則做s->t

下面我來試著證明一下這個貪心的正確性
對于t棧棧頂元素x，如果已經比s棧中所有元素都小了，那么將x轉入u棧一定是最優決策；
如果s棧中最小的元素和x相同，那么將x轉入u棧不會讓結果變得更糟（反之則有可能）
如果s棧中最小的元素小于x，應該把這個比較小的元素放到t棧中，所以做s->t

，min_s【i】=x，表示第i個位子后邊最小的字符是x.

AC代碼：

#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<string> #include<queue> #include<map> #include<stack> #include<set> #include<ctime> using namespace std; typedef long long ll; #define INF 0x3f3f3f3f #define max 2000char min_s[100080];int main() {string ss;while (cin >> ss){int len = ss.size();for (int i = len - 1; i >= 0; --i){if (i == len - 1)min_s[i] = ss[i];elsemin_s[i] = min(min_s[i + 1], ss[i]); //維護 位置i后邊最小的字符}stack<char>t;for (int i = 0; i < len; i++){if (t.empty()) //為空的話就將一個字符讀入t.push(ss[i]);else{while (!t.empty()){int u = t.top() ;if (u <= min_s[i]) //如果當前字符是比i位置后邊的字符小或等于的話就可以輸出了。{cout << t.top();t.pop();}else //否則直接停止break;}t.push(ss[i]); //將這個字符壓入棧}}while (!t.empty()){cout << t.top();t.pop();}cout << endl;}return 0;}

總結

以上是生活随笔為你收集整理的Codeforces 797C Minimal string【贪心】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。