贪心算法问题

Question

删数问题：键盘输入一个高精度的正整数你（n<=240）,去掉其中任意s个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的n和s，寻找一种方案，使得剩下的数字组成的新数最大。请在程序内容写上注释，内容包括编程日期和姓名学号
输入说明：
n
s
输出说明：
最后剩下的最大数
输入样例：
178543
4

Answer 1

//身为大一菜鸟的我曾错了n次的题
//算法是从头开始扫过去，若当前扫到的数比下一个大，则删，删后回退到上一个未被删的数继续，直到删完指定数或扫到最后一个元素，若删不够指定的数，则此刻数组肯定是递增的，所以只要从后向前删至足够数量便行了

#include<iostream>
#include<string.h>
using namespace std;
char str[250];
int a[250];
int b[250];

int main(){
int i, len, k, l, r, c, t, f;
do{
f = 0;
cin >> str;
if (str[0] == '0')
break;
len = strlen(str);
cin >> k;
for (i = 0; i<250; i++){
a[i] = i + 1;
b[i] = i - 1;
}
c = 0;
l = 0;
for (r = 1; str[r] != '\0';){
if (c >= k)
break;
if (str[r] - str[l] >= 0){
l = a[l];
r = a[r];
}
else{
c++;
if (b[l] != -1){
a[b[l]] = r;
b[r] = b[l];
l = b[l];
}
else{
f = 1;
b[r] = -1;
a[0] = r;
l = a[l];
r = a[r];
}
}
}
t = r - 1;
for (; c<k; c++){
a[b[t]] = r;
t = b[t];
}
if (f == 0)
cout << str[0];
i = 0;
for (i = a[i]; i<len; i = a[i]){
cout << str[i];
}
cout << endl;
} while (1);
return 0;
}本回答被提问者采纳