首页 > 代码库 > [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 (贪心乱搞)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。