贪心题——删数问题

来源：百度知道 编辑：UC知道 时间：2024/05/17 00:51:44
从键盘输入一个高精度正整数N，任意去掉S个数字，把剩下的数字组合成一个新的高精度正整数M（次序不变）。
输入：N（≤20位），S（1≤S≤10）
例如：输入 51428397 5
输出 123

要C++的程序，C的不要。
不能用枚举搜索法、动态规划等，只能用贪心。（希望运行速度能快点。）

最好给上分析。
那最后的数字呢51428397里的7怎么删呢?

前面的数比它后面的数大就删掉
如果整个数已经是从小到大排列，就直接把末尾的数删掉
#include <iostream>

using namespace std;

const int Limit_Size = 21;

char num[ Limit_Size ];
int S, len;

void init( )
{
cin >> num >> S;
len = strlen( num );
}

void work( )
{
int i, j, k;
for ( i = 0; i < S; i++ )
{
for ( j = 0; j < len - 1; j++ )
if ( num[ j ] > num[ j + 1 ] )
{
for ( k = j; k < len - 1; k++ )
num[ k ] = num[ k + 1 ];
break;
}
len--;
}
}

void print( )
{
int i;
if ( len <= 0 )
cout << 0;
else
for ( i = 0; i < len; i++ )
cout << num[ i ];
cout << endl;
}

int main( )
{
init( );
work( );
print( );
return 0;
}