首页 > 代码库 > 删数问题
删数问题
删数问题
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 72 Accepted Submission(s) : 16
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
键盘输入一个高精度的正整数n(≤240位),去掉其中任意s个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的n和s,寻找一种方案,使得剩下的数字组成的新数最小。
Input
第一行为测试示例个数n,对于每个测试示例分别有两行,第一行为一个高精度的正整数n,第二行为去掉的数字个数s。
Output
最后剩下的最小数。
Sample Input
1 178543 4
Sample Output
13
//经典的贪心问题。
每一步总是选择一个使剩下的数最小的数字删除,即按高位到低位的顺序搜索,若各位数字递增,则删除最后一个数字;否则删除第一个递减区间的首字符,这样删一位便形成了一个新的数字串。然后回到串首,按上述规则再删除下一个数字
#include<iostream> #include<string> using namespace std; int main() { int t,cnt,i,j,len,fla; string s; cin>>t; while(t--) { cin>>s>>cnt; len=s.length(); for(i=0;i<cnt;i++) { fla=len-1; for(j=0;j<len-1;j++) { if(s[j+1]<s[j]){fla=j;break;} } for(j=fla;j<len-1;j++) { s[j]=s[j+1]; } len--; } if(len<1) cout<<0<<endl; else { for(i=0;i<len;i++) { if(s[i]>'0') { fla=i;break;} } for(i=fla;i<len;i++) cout<<s[i]; cout<<endl; } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。