洛谷 P1106：删数标题 ← 贪婪算法

【标题来源】
https://www.luogu.com.cn/problem/P1106

【标题描述】
键盘输入一个高精度的正整数 n（不凌驾 250 位），去掉其中恣意 k 个数字后剩下的数字按原左右次序将构成一个新的非负整数。编程对给定的 n 和 k，探求一种方案使得剩下的数字构成的新数最小。

【输入格式】
输入两行正整数。
第一行输入一个高精度的正整数 n。
第二行输入一个正整数 k，表现须要删除的数字个数。

【输特别式】
输出一个整数，末了剩下的最小数。

【输入样例】
175438 
4

【输出样例】
13

【阐明/提示】
用 len(n) 表现 n 的位数，包管 1≤k<len(n)≤250。

【算法分析】
● s.erase(pos,n)  // 删除从 pos 开始的 n 个字符。

1. #include<bits/stdc++.h>
2. using namespace std;
4. int main() {
5.     string s;
6.     cin>>s;
7.     s.erase(2,6);
8.     cout<<s;
9.     return 0;
10. }
12. /*
13. in:
14. abcdefghijklmn
16. out:
17. abijklmn
18. */

复制代码

【算法代码】

1. #include<bits/stdc++.h>
2. using namespace std;
4. string s;
5. int n;
7. int main() {
8.     cin>>s>>n;
9.     while(n--) {
10.         for(int i=0; i<s.size(); i++) {
11.             if(s[i]>s[i+1]) {
12.                 s=s.erase(i,1);
13.                 break;
14.             }
15.         }
16.     }
18.     if(s.size()==1) {
19.         cout<<s[0];
20.         return 0;
21.     }
23.     int len=0;
24.     while(s[len]=='0') len++;
25.     for(int i=len; i<s.size(); i++) {
26.         cout<<s[i];
27.     }
29.     return 0;
30. }
32. /*
33. in:
34. 175438
35. 4
37. out:
38. 13
39. */

复制代码

【参考文献】
https://www.luogu.com.cn/problem/solution/P1106
https://www.jb51.net/article/222705.htm


 

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。