管他那么多，贪心最大嘛
题意：给两个长度<1e4一样的字符串a,b。求一个串长一样的最小字典序字符串c，使得(c,a)==(c,b)，(x,y)是指x与y的海明距离。
点击查看思路
思路：贪心即可。
贪心的每次放字典序最小的字母，满足修改量 <=后面的不相等字母对数即可放。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
#include<bits/stdc++.h>
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
typedef pair<ll,ll> P;
const ll maxn=1e4+11;
ll sum[maxn];
string ar,br;
void solve(){
ll l=ar.length();
sum[l]=0;
for(ll i=l-1;i>=0;i--){
sum[i]=sum[i+1]+(ar[i]!=br[i]);
}
ll cnt1=0,cnt2=0;
for(ll i=0;i<l;i++){
for(ll j=0;j<26;j++){
char x='a';
x+=j;
ll flag1=0,flag2=0;
if(x!=ar[i]) flag1++;
if(x!=br[i]) flag2++;
if(abs(cnt1+flag1-cnt2-flag2)<=sum[i+1]){
cout<<x;
cnt1+=flag1,cnt2+=flag2;
break;
}
}
}
cout<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
ll ca;cin>>ca;
ll t=1;
while(ca--){
cin>>ar>>br;
cout<<"Case "<<t++<<": ";
solve();
}
return 0;
}
|