贪心算法——删数问题（修改后）

本文主要是介绍贪心算法——删数问题（修改后），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

要求：一个m位的数，去掉其中任意s个数，剩下的数按原次序组成一个新的数，要求编写程序是的重新组合的那个数最小。

主要思路：
1、确定最高位：现在前s+1个数中找到最小的那个数，同时将所找到的这个数之前的数全部删掉。（因为删除s个数，所以最高位的那个数肯定在前s+1之中）
2、按同样的方法依次确定第i位数，但是数字比较的范围要缩小到从上一个确定的数后一位数到第s+i位数。（一共比较s次）
3、在删数的过程中要判断当前是否已经删满s个数了。
4、若s次比较完之后删除的数不满s个（假如只删了n个），那就要将最后s-n个数删除。

C++代码：
修改后的代码：

#include <iostream>
#include <string.h>
#include <stdio.h>
using  namespace std;void deletea(char *num,int j,int n){for(int i=j;i<strlen(num)-n;i=i+n){num[i]=num[i+n];}
}int length(char *num){return strlen(num);
}void fun(char *num,int k,int *pos){int i=0,j=0,jl=-1;while(i<k&&j<length(num)){while(num[j]<=num[j+1])j++;if(j<length(num)){deletea(num,j,1);if(j>jl)pos[i]=j+i;   //加i是因为前面删除的时候位置会改变elsepos[i]=pos[i-1]-1;   //删除i之后比较i-1和i+1的时候i-1比i+1大的情况i++;jl=j;j=j-1;          //比较i-1和i+1}}if(i!=k){                //比较完之后删除的数字不满k个的情况，那就从最后将少的那几个数删掉for(int m=i;m<=k;m++){deletea(num,length(num)-m,1);pos[i]=length(num)-m;i++;}}
}int main(){char *num;int *pos;   //pos存放删除的数的位置int k;cin>>k;pos=new int[k+1];num=new char[100];fflush(stdin);cin>>num;int len=length(num);fun(num,k,pos);for(int i=0;i<len-k;i++)cout<<num[i];cout<<endl;for(int i=0;i<k;i++)cout<<pos[i];cout<<endl;return 0;
}

修改前错误代码：

#include <iostream>
using namespace std;
void fun(char a[],int m,int s)
{int i,j,dcount=0,pos,key=0;char mini;for(i=0;i<s;i++){if(dcount==s)           //判断当前是否已经删除完成break;mini='z';for(j=key;j<=s+i;j++)   //从最高位开始确定{if(a[j]<mini){mini=a[j];pos=j;}}for(j=key;j<pos;j++){a[j]='*';dcount++;}key=pos+1;             //确定下一个位数开始的位置}if(dcount!=s)              //删除最后几位的情况{for(i=m-1;i>=m-s+dcount;i--)a[i]='*';dcount=s;}
}
int main()
{char *a;int m,s,i;cout<<"请输入原数据长度以及删除位数:"<<endl;cin>>m>>s;a=new char[m];cout<<"请输入数据:"<<endl;cin>>a;fun(a,m,s);for(i=0;i<m;i++)if(a[i]!='*')cout<<a[i];return 0;
}