4-2 删数问题 (30 分)
给定n位正整数a，去掉其中任意k≤n 个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a和正整数 k，设计一个算法找出剩下数字组成的新数最小的删数方案。如果数字最前面有0不输出。

输入格式:
第 1 行是1 个正整数 a。第 2 行是正整数k。

输出格式:
输出最小数。

输入样例:
在这里给出一组输入。例如：

178543 
4 

5001 
1

123456 
2

109 
1

输出样例:
在这里给出相应的输出。例如：

13

1

1234

9

算法一

我的思路：
以178543为例，有6个数字，题目要求删除4位，也就是最后剩下两位，这二位数字要求是所有二位数字之中最小的。第一位数字肯定是这原来6位数字中最小的一个，比如这题的1，因为题目要求按数字的顺序，所以找到第一位最小的数，就要从第个数的位置开始找第二个最小的数。因为无论如何都要有两个数，为了保证一定会有两个数，第一个最小数的查找要从0到len-2，因为就算找不到，也能保证len-2和len-1这两个数是结果。同理因为已经找到一个数了，所以第二个数的查找要从这题的1到len-1；
代码如下：

#include<bits/stdc++.h>
using namespace std;
string s;
int len;
int findmin(int k,int c){
	int min=s[k]-'0',j=k;
	for(int i=k;i<=len-c;i++){
		if(s[i]-'0'<min){
			min=s[i]-'0';
			j=i;
		}
	}
	return j;
}
int main(){	
	cin>>s;
	len=s.size();
	vector<int> v;
	int k;
	cin>>k;
	int last=len-k;
	int c=0,pre=0,tmp=last;
	while(c<last){
		int a=findmin(pre,tmp); 
		v.push_back(s[a]-'0');
		pre=a+1;
		c++;
		tmp--;
	}
	int begin=0;
	for(int i=0;i<v.size();i++){
		if(v[i]==0){
			if(begin!=0){
				cout<<v[i];
			}
		}else{
			cout<<v[i];
			begin=1;
		}
	}
}

查找最小数的时间复杂度是O(n),总共n-k次。总体时间复杂度O(n^2)?

算法二：

网上的思路：
从删数的角度，找到非递减的最后一个数，或者说是第一个递减序列的第一个数，把它删掉。然后又从头开始查找。
比如178543，假设删掉一个数，那就是1，7，8最后的8，如果删掉的不是8，分两种情况，一是8前面的数，二是8后面的数。如果是后面的数，则8是这五个数的第三位，如17853，8之后的数一定比8小，也就是如果把8和这个更小的数替换，比如17543，第三位肯定比8小，整体也比这五位数小；同理删除前面的数也一样，因此贪心思路正确。
代码如下：

#include<bits/stdc++.h>
using namespace std;
char s[101];
int len;
int main(){
	cin>>s;	
	int k;	
	cin>>k;
	while(k>0){
		int i=0;
		int a=strlen(s);
		while(i<a&&s[i]<s[i+1]){
			i++;
		}
		while(i<a){
			s[i]=s[i+1];
			i++
		}
		k--;
	}
	int i=0;
	int a=strlen(s);
	while(s[i]=='0'&&i<a){
		i++;
	}
	if(i==a){
		cout<<0;
	}else{
		for(;i<a;i++){
			cout<<s[i];
		}
	}
	return 0;
}

时间复杂度为O(k*n)

对贪心算法的理解

贪心，因为符合直觉，所以很多问题都可以用贪心解决。但也因此没有固定的模式，思路比较发散。而且贪的是什么，往往很难找到和做严格的证明。就像人生，很多人走在人生的路上，一心都认为最应该贪金钱，最终真的能找到人生的解吗，如果贪的是其他，能不能做出人生这道题呢，又如何证明这一定是对的呢。做每道题，都像在探索人生。而这做题之路，还有很长的距离要走。