题目大意:

首先,给你两个字符串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]);
    }
}