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)。

理解：贪心算法只从当前最优解出发，并不一定能得到全局最优解，此世就要寻找局部最优且全局最优策略，但这需要数学证明。实际上贪心算法就是为了解决动态规划的开销问题，但都需要事先数学证明，得到验证的策略只适合同类问题。