首页 > 代码库 > 解题报告—— 2018级2016第二学期第五周作业 删数问题
解题报告—— 2018级2016第二学期第五周作业 删数问题
解题报告—— 2018级2016第二学期第五周作业
删数问题
描述
键盘输入一个高精度的正整数n(<=240位),去掉其中任意s个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的n和s,寻找一种方案,使得剩下的数字组成的新数最小。
输入n
s输出最后剩下的最小数样例输入
178543 4
样例输出
13
分析:
这题题目上已表明是贪心算法;
原本最容易产生的错误贪心准则是删去其中最大的数字;
但通过简单举例便可得之,这种贪心准则要漏洞;
通过简单的计算举例发现
如果这个数是一位比一位大的话是最好的最小的;
所以如果哪一位比后面的数大那说明这个数就要删除;
如果找不到,便删最后一个;
那么贪心准则便有了;
接下来我们进行读入;
我采用的是用字符串读的;
因为这样好删除,并且根据ascll码可以直接比较;
但注意每次都要删除时len--;
之后注意输出要删0;
我们就应该
while(p<len-1&&st[p]==‘0‘)p++;
这样来判断从哪开始输出;
这样就ac了;
代码:
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;
char st[1000];
int n;
int len;
void readp(){
gets(st);
cin>>n;
len=strlen(st);
}//读入
void deal(){//删除
bool flag=false;//无罪假定
for(int i=0;i<len-1;i++){
if(st[i]>st[i+1]){
for(int j=i;j<len;j++)
st[j]=st[j+1];
len--;
flag=true;
break;
}
}
if(!flag)len--;//如果没有删最后一位
}
void printp(){
int p=0;
while(p<len-1&&st[p]==‘0‘)p++;//删0
for(int i=p;i<len;i++)cout<<st[i];
cout<<endl;//输出
}
int main(){
readp();
while(n--){
deal();
}//几次判断
printp();
return 0;
}
解题报告—— 2018级2016第二学期第五周作业 删数问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。