UVA11491-Erasing ans Winning(贪心)

2021-07-10 11:08

阅读：498

For each test case in the input your program must produce one single line in the output, containing the highest prize Juliano can win.

Sample Input

4 2
3759
6 3
123123
7 4
1000000
0 0

Sample Output

79
323
100

题解：这个题贪心的思路很明显，但是不同的贪心策略在效率上差距很大（我的效率就很差），我的思路很直接，要保留d个，那么答案的最高位肯定是前d+1个数的最大值，找到之后删去它前面的，继续找，如果删到最后发现d还是大于0，就说明在已经找到的答案串中还需要继续删，就把答案串当作原始串继续删，最后输出即可。交上去虽然A了，但是用了770ms，然后我惊奇地发现大佬们都是0ms过，找了找题解，发现了很好的做法（orz），大家可以作为参考。

博客的链接如下：

https://www.cnblogs.com/zyb993963526/p/6354314.html

 1 #include  2 
 3 using namespace std;
 4 
 5 int n, d;
 6 
 7 int main()
 8 {
 9     //freopen("input.txt", "r", stdin);
10     while (~scanf("%d%d", &n, &d) && (n || d)) {
11         string num, ans = "";
12         cin >> num;
13 
14         bool flag = false;
15         int pos = 0, len = num.length();
16         while (d) {
17             if (d >= len-pos) {
18                 flag = true;
19                 d -= len - pos;
20                 num = ans;
21                 continue;
22             }
23             char Max = 0;
24             int i, p;
25             for (i = pos; i 1 && i ) {
26                 if (Max  num[i]) {
27                     Max = num[i];
28                     p = i;
29                 }
30             }
31             ans += num[p];
32             d -= p - pos;
33             pos = p + 1;
34         }
35 
36         if (!flag) ans += num.substr(pos, num.size() - pos);
37         cout  endl;
38     }
39     return 0;
40 }

上一篇：Windows下安装PHP开发环境

下一篇：Windows 7/8/10 系统下Laravel框架的开发环境安装及部署详解（Vagrant + Homestead）

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：UVA11491-Erasing ans Winning(贪心)
文章链接：http://soscw.com/essay/103203.html

亲，登录后才可以留言！

UVA11491-Erasing ans Winning(贪心)

Sample Input

Sample Output

评论

热门文章

推荐文章

最新文章

置顶文章