题意:给一个 s 串和 t 串, s 串中有若干问号,问如何填充问号使得 s 串中字母可以组成最多的 t 串。输出填充后的 s 串。
思路:想了下感觉直接怼有点麻烦,要分情况:先处理已经可以组成 t 串的部分,然后处理 s 串中可以利用的部分,如果还有问号剩余,再直接怼。但如果用二分写就很直观了,直接看最多能组成多少个 t 串。
居然踩了long long的坑感觉自己宛若一个zz。check函数中的计算要用long long防止溢出= =(明明大水题的说。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=1e6+;
char s[N],t[N];
int cntS[],cntT[],cntQ;
bool check(int x){
ll tmp=;
for(int i=;i<;i++) if(cntT[i]){
tmp+=max(0LL,1LL*x*cntT[i]-cntS[i]);
}
return tmp<=cntQ;
}
int main(){
scanf("%s%s",s,t);
int ls=strlen(s),lt=strlen(t);
for(int i=;i<ls;i++)
if(isalpha(s[i]))
cntS[s[i]-'a']++;
else cntQ++;
for(int i=;i<lt;i++)
cntT[t[i]-'a']++;
int l=,r=N,x=;
while(l<=r){
int mid=(l+r)>>;
if(check(mid)){
l=mid+;
x=mid;
}else r=mid-;
}
int id=;
for(int i=;i<ls;i++){
if(s[i]=='?'){
while(id<&&cntS[id]>=cntT[id]*x) id++;
if(id<){
printf("%c",'a'+id);
cntS[id]++;
}
else putchar('a');
}else printf("%c",s[i]);
}
puts("");
return ;
}