BZOJ 3799 字符串重组 贪心模拟乱搞

字符串长度<=5000

传送门

首先肯定是有贪心的想法的，

我们要求比T串大且最小，那么有以下一些简单的思想：

1.和T串的最长公共前缀尽量长。

2.比T串某一位大的那个字符尽量小。

3.比T串某一位大的那个字符之后，后面的排列从小到大。

记录一下对于T的每一位是否在S里面存在Equal和Bigger即可。

然后特殊情况（其实样例就是），既没有Equal也没有Bigger，

这种情况再找一个合法的即可。

主要考验模拟的细节吧……

#include<bits/stdc++.h>
using namespace std;
const int N=5005;
char S[N],T[N];
int LS,LT;
bool p[N];
int Equal[N],Bigger[N];
int main(){scanf("%s",S+1);scanf("%s",T+1);LS=strlen(S+1),LT=strlen(T+1);sort(S+1,S+1+LS);string ans=""; bool flag=0;for (int i=1;i<=LT;i++){int tmp=0;for (int j=1;j<=LS;j++)if (!p[j] && S[j]==T[i]){tmp=j;break;}if (tmp) Equal[i]=tmp,p[tmp]=1,ans+=S[tmp];tmp=0;for (int j=1;j<=LS;j++)if (!p[j] && S[j]>T[i]){tmp=j;break;}if (tmp){Bigger[i]=tmp;if (!Equal[i]) p[tmp]=1,ans+=S[tmp];}if (!Equal[i] && Bigger[i]) break;if (!Equal[i] && !Bigger[i]){flag=1;break;}}if (flag){int tt=ans.size(),tmp=0;for (int i=LT;i;i--)if (Bigger[i]){tmp=i;break;}if (!tmp){puts("-1");return 0;}for (int i=0;i<tmp-1;i++) printf("%c",ans[i]);printf("%c",S[Bigger[tmp]]);for (int i=1;i<=LS;i++)if (!p[i]) printf("%c",S[i]);puts("");return 0; }cout<<ans;for (int i=1;i<=LS;i++)if (!p[i]) printf("%c",S[i]);puts("");return 0;
}