题目大意:
首先,给你两个字符串s,t,然后s里面有’?’,t里面没有,现在就是问你给s里的这些’?’赋什么值,才能让s里这些字母有一种排序可以让t尽量多的出现在s里面。
分析:
如果我没理解错题意的话,应该就是给t里面各个字母出现的次数记个数,然后把’?’按比例赋值,使得能组合出来的t尽可能多就好了。
代码:
#include<bits/stdc++.h>
#define maxn 1000500
#define inf 0x3f3f3f3f
using namespace std;
char s[maxn],t[maxn];
int num=0;
int num_s[30]={0},num_t[30]={0},appear[30]={0};
struct point
{
int time;
int pow;
}a[30];
int main()
{
scanf("%s%s",s,t);
int temp=strlen(s);
for(int i=0;i<temp;i++)
{
if(s[i]=='?')num++;
else num_s[s[i]-'a']++;
}
temp=strlen(t);
for(int i=0;i<temp;i++)
{
num_t[t[i]-'a']++;
}
for(int i=0;i<30;i++)
{
if(num_t[i]==0)
{
a[i].pow=inf;
continue;
}
a[i].pow=num_s[i]/num_t[i];
a[i].time=num_s[i]%num_t[i];
}
//for(int i=0;i<26;i++)printf("%d ",a[i].time);
while(num--)
{
int m=0;
for(int i=0;i<26;i++)
{
if(a[i].pow<a[m].pow||a[i].pow==a[m].pow&&a[i].time<a[m].time)m=i;
}
a[m].time++;
appear[m]++;
if(a[m].time==num_t[m])
{
a[m].pow++;a[m].time=0;
}
}
temp=strlen(s);
int now=0;
//for(int i=0;i<26;i++)printf("%d ",appear[i]);
for(int i=0;i<temp;i++)
{
if(s[i]=='?')
{
while(appear[now]==0)now++;
s[i]=(char)now+'a';
appear[now]--;
}
printf("%c",s[i]);
}
}