BZOJ 3799 字元串重組 貪心模拟亂搞

Description

給出一個字元串S,現希望對它進行重新組合得到

一個字元串，其比T大且是字典序最小的。

Input

輸入第一行為S，第二行為T

Output

輸出重組後的結果，如果不存在輸出-1

Sample Input

abad

bob

Sample Output

daab

HINT

字元串長度<=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;
}