题目大意
奥列格和伊戈尔打算开一个公司，他们对于公司的取名有不同的意见。
他们两个各有一个长度相等的字符串，公司的名字最初是全由 \(\texttt{?}\) 构成的一个字符串，两人轮流操作，在自己的字符串中选出一个字符取代公司名字中的某一个 \(\texttt{?}\)，使用后该字符就在当前操作者的字符串中消失了。
游戏结束当且仅当每一个 \(\texttt{?}\) 都被两人的字符取代。
奥列格想要使得公司名字的字符串字典序最小，伊戈尔想要让公司名字的字符串字典序最大。
假设两人都进行最优操作，请求出操作结束后的公司名字。
思路
首先有一个比较显然的贪心思路。
为使得最终字符串的字典序最小，奥列格每次选取自己字典序最小的字符，放在能够放置的最前面位置，伊戈尔每次选取自己字典序最大的字符，也放在能够放置的最前面位置。
但这样的贪心是有问题的，会错在第 \(6\) 个测试点。
考虑这样一种状况，奥列格剩下的字符中最小的都已经大于伊戈尔手中最大的，那么如果奥列格再往最前面放显然就是错的了。
这种状况下奥列格怎么最优操作呢？他可以把自己的字符往后放，这样伊戈尔就不得不把他小于奥列格的字符往前放。
那么在这种条件下，二者的最优策略就是把自己的字符从后往前放。
所以当奥列格仍然有小于伊戈尔的字符时，采取第一种策略，否则采取第二种策略。
具体代码可以用 deque 维护，支持取头尾元素，十分的方便。
时间复杂度 \(\operatorname{O}(n)\)。
Code
#include <bits/stdc++.h>
using namespace std;
int n;
string s,t;
deque<char> q1,q2;
int main() {
cin >> s >> t;
n = s.size();
sort(s.begin(),s.end());
sort(t.begin(),t.end());
reverse(t.begin(),t.end());
for(int i = 0;i < (n + 1) / 2; i++)
q1.push_back(s[i]);
for(int i = 0;i < n / 2; i++)
q2.push_back(t[i]);
string ansl = "",ansr = "";
bool flag = 0;
for(int i = 1;i <= n; i++) {
if(i % 2) {
if(!q2.empty() && q1.front() >= q2.front())
flag = 1;
if(flag) {
ansr += q1.back();
q1.pop_back();
}
else {
ansl += q1.front();
q1.pop_front();
}
}
else {
if(!q1.empty() && q1.front() >= q2.front())
flag = 1;
if(flag) {
ansr += q2.back();
q2.pop_back();
}
else {
ansl += q2.front();
q2.pop_front();
}
}
}
reverse(ansr.begin(),ansr.end());
string ans = ansl + ansr;
cout << ans;
return 0;
}