最简单的贪心算法-删除数字有关问题
最简单的贪心算法--删除数字问题
给出一个N个数字的数字序列,删除n(n<N)个数字后按原左右次序组成新的正整数,使剩下的数字组成的正整数最大。
分析:将数字序列保存在数组中,每删除一个数字都使剩下的数字组成的正整数最大,并且以它作为下一个删除对象。删除n个数字的全局最优解包含删除一个数字的子问题的最优解。每次删除一个数字,从左往右每相邻的两个数字比较,若左边小于右边则删除左边的那个数字,否则比较下一对数字。每次删完一个数字,后面的元素前进一个位置,并且从头开始比较。
代码:
#include "stdafx.h" #include <iostream> using namespace std; int _tmain(int argc, _TCHAR* argv[]) { int i,count; int numberA[200]; char numberB[200]; cin>>numberB; for (count=0,i=0;numberB[i]!='\0';i++) { count++;//记录实际输入数字的个数 numberA[i]=numberB[i]-48;//将字符转换成数字放进数组A中 } int DelNumCount;//要删除数字个数 cout<<"输入要删除的个数:"; cin>>DelNumCount; cout<<"以上"<<count<<"位整数中删除"<<DelNumCount<<"个数字分别为:"<<endl; i=0; int flag=0,j; int delcount=0;//记录删除个数的临时变量 while( DelNumCount>delcount && flag==0 )//没有删够数量,还没有到最后一个数字 { i++; if (numberA[i-1] < numberA[i])//前一个数字比后一个数字小,删 { cout<<numberA[i-1]<<" "; for (j=i-1;j<=count-delcount-2;j++)//后面的数字依次往前进一格 { numberA[j]=numberA[j+1]; } delcount++;//删除数量增1 i=0;//从头开始查递增区间 } if (i==count-delcount-1)//如果是最后一个数字 { flag=1; } } cout<<"\n删除后所得最大数为:"; for (i=0;i<count-DelNumCount;i++)//依次输出数组中各个数字 { cout<<numberA[i]; } cout<<endl; return 0; }