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
代码：
搭档：
#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;
}
}
}
我的：
#include <iostream>
#include <queue>
#include <string.h>
#include <algorithm>
using namespace std;
int main()
{
int a[245], count=0, s, leng;
string ss;
memset(a, -1, sizeof(a));
getline(cin, ss);
scanf ("%d", &s);
for (int i=0; i<ss.length(); i++) {
a[i] = ss[i] - '0';
}
leng = ss.length();
for (int i=0; i<s; i++) { //循环s遍
for (int j=0; j<leng-1; j++) {
if (a[j] > a[j+1]) {
for (int k=j; k<leng-1; k++) { //删除
a[k] = a[k+1];
}
break;
}
}
leng--;
}
for (int i=0; i<leng && a[i]==0; i++) { //记录多余0的数目
count++;
}
if (count == leng) { //全为0时
printf ("0");
} else {
for (int i=count; i<leng; i++) {
printf ("%d", a[i]);
}
}
return 0;
}
贪心策略：
搭档：从最左端以删除数为范围寻找最小数字，加入新数组并记录位置；再从记录位置以范围+1找最小数，并记录；经过所需保留数字个数次后停止。
我/CSDN：从最高位开始扫描，删除相邻且前者比后者大的前者。
复杂度：最坏O(n^2)，期望O(nlogn)。
理解：贪心算法只从当前最优解出发，并不一定能得到全局最优解，此世就要寻找局部最优且全局最优策略，但这需要数学证明。实际上贪心算法就是为了解决动态规划的开销问题，但都需要事先数学证明，得到验证的策略只适合同类问题。