CF 254C(易位构字法）

C. 易位构字法

time limit per test

memory limit per test

input

output

异位构字就是把一个字符串的顺序改变，可以得到另一个字符串.

s 和 t ,至少修改 s s 和 t s 易位后字典序最小的。

Input

s, t. 长度不超过 10⁵

Output

 s 修改后字典序最小的字符串。

Sample test(s)

input

ABA CBA

output

1 ABC

input

CDBABC ADCABD

output

2 ADBADC

Note

s 可改成: "ADBADC", "ADDABC", "CDAABD", "CDBAAD", "CDBADA", "CDDABA", "DDAABC", "DDBAAC". 字典序最小的是 "ADBADC".

直接处理字符串。

program word;
const
   maxn=100000;
var
   s,t:ansistring;//->ansistring
   n,i,j,ans,size,head:longint;
   pass,a1,a2,deln:array['A'..'Z'] of longint;
   add:array[1..26] of char;
   addn:array[1..26] of longint;
   ic:char;
begin
   assign(input,'input.txt');
   assign(output,'output.txt');
   reset(input);
   rewrite(output);
   fillchar(a1,sizeof(a1),0);
   fillchar(a2,sizeof(a2),0);
   fillchar(pass,sizeof(pass),0);
   fillchar(deln,sizeof(deln),0);
   readln(s);
   readln(t);
   n:=length(s);
   for i:=1 to n do inc(a1[s[i]]);
   for i:=1 to n do inc(a2[t[i]]);

   size:=0;
   ans:=0;
   for ic:='A' to 'Z' do
      if a2[ic]>a1[ic] then
      begin
         inc(size);
         add[size]:=ic;
         addn[size]:=a2[ic]-a1[ic];
         inc(ans,addn[size]);
      end
      else if a2[ic]<a1[ic] then
      begin
         deln[ic]:=a1[ic]-a2[ic];
      end;

   writeln(ans);
   head:=1;
   for i:=1 to n do
   begin
      inc(pass[s[i]]);
      if deln[s[i]]>0 then
      begin
         if (add[head]<s[i]) or (deln[s[i]]>a1[s[i]]-pass[s[i]]) then
         begin
            dec(deln[s[i]]);
            s[i]:=add[head];
            dec(addn[head]);
            if addn[head]=0 then inc(head);
         end;
      end;
   end;
   writeln(s);
   close(input);
   close(output);
end.