首页 > 代码库 > 贪心3--删数问题
贪心3--删数问题
贪心3--删数问题
一、心得
二、题目及分析
题目：
键盘输入一个高精度的正整数ｎ（<=240位），
去掉任意ｓ个数字后剩下的数字按原左右次序将组成一个新的正整数。
编程对给定的ｎ和ｓ，寻找一种方案，使得剩下的数最小。
Simple Input
178543
4
Simple Output
13
思路：
每一步总是选择一个使剩下的数最小的数字删除，即按高位到低位的顺序搜索，若各位数字递增，则删除最后一个数字；否则删除第一个递减区间的首字符，这样删一位便形成了一个新的数字串。然后回到串首，按上述规则再删除下一个数字
三、代码及结果
1 #include <iostream> 2 #include <string> 3 using namespace std; 4 int main(){ 5 string s; 6 cin>>s; 7 int n; 8 cin>>n; 9 int len=s.length(); 10 int a[300]; 11 for(int i=0;i<len;i++){ 12 a[i+1]=s[i]-‘0‘; 13 } 14 for(int i=1;i<=n;i++){ 15 for(int j=1;j<len;j++){ 16 if(a[j]>a[j+1]){ 17 for(int k=j;k<len;k++){ 18 a[k]=a[k+1]; 19 } 20 break; 21 } 22 } 23 len--; 24 } 25 for(int i=1;i<=len;i++){ 26 cout<<a[i]; 27 } 28 cout<<endl; 29 return 0; 30 }
贪心3--删数问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。