题意:
给出n个串(n为偶数);
要构造一个串,使n串中有一半小于等于它,另外一半大于它;
要求这个串长度尽量小,同时字典序小;
一开始我的优先级是放左 其实优先级是放左加一。
如 AAAA
AABB
答案为AAB 按照我一开始的做法 答案为AAAA
还有两个细节 如果到L的末尾 那么放L的末尾
如果 Li为 Z 那么就不能放Z+1了
ans不可能大于L.size 因为 和L一样为最低要求值
ans不可能大于R.size 不然就比R大了 这中间一定有答案 所以根本不用考虑R.size
string 直接加很方便
#include<bits/stdc++.h> using namespace std; #define N 200000+5 int n,w; string a[N]; int main() { int n; while(scanf("%d",&n),n) { for(int i=0;i<n;i++) cin>>a[i]; sort(a,a+n); string R=a[n/2]; string L=a[n/2-1]; string ans=""; for(int i=0;i<L.size();i++) { if( i<L.size()-1&&L[i]!='Z') { ans+=L[i]+1; if(ans<R)break; ans[i]--; } else ans+=L[i]; } cout<<ans<<endl; } return 0; }