首页 > 代码库 > 解题报告—— 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第二学期第五周作业 删数问题