首页 > 代码库 > [CF825D] Suitable Replacement (贪心乱搞)

[CF825D] Suitable Replacement (贪心乱搞)

题目链接:http://codeforces.com/problemset/problem/825/D

题意:给两个字符串s t,s中有一些问号。现在问号可以替换为任意字符,s字符串可以任意换位置,希望让t在s中出现次数最多。

统计s中各个字符出现次数,一直扫t,用s中与t相同字符抵消,不能抵消就用问号抵消。直到问号没有为止。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef pair<int, int> pii;
 5 const int maxn = 1000100;
 6 int a[256];
 7 char s[maxn], t[maxn];
 8 vector<int> pos;
 9 
10 signed main() {
11     // freopen("in", "r", stdin);
12     while(~scanf("%s%s",s,t)) {
13         memset(a, 0, sizeof(a));
14         int n = strlen(t);
15         pos.clear();
16         for(int i = 0; s[i]; i++) {
17             if(s[i] != ?) a[s[i]]++;
18             else pos.push_back(i);
19         }
20         if(!pos.size()) {
21             puts(s);
22             continue;
23         }
24         int k = 0;
25         while(k < pos.size()) {
26             for(int i = 0; t[i]; i++) {
27                 if(a[t[i]]) a[t[i]]--;
28                 else s[pos[k++]] = t[i];
29                 if(k >= pos.size()) break;
30             }
31         }
32         puts(s);
33     }
34     return 0;
35 }

 

[CF825D] Suitable Replacement (贪心乱搞)