删数问题

一、试 题
键盘输入一个高精度的正整数N，去掉其中任意S个数字后剩下的数字按原左右次序将组
成一个新的正整数。编程对给定的N和S，寻找一种方案使得剩下的数字组成的新数最小。
　　输出应包括所去掉的数字的位置和组成的新的正整数。（N不超过240位）
　　输入数据均不需判错。
二、算法分析

　　首先我们必须注意，试题中正整数Ｎ的有效位数为２４０位，而计算机中整数有效位（
包括符号位）充其量也不过１１位，无论如何也达不到试题的数位要求。因此，必须采用可
含２５６个字符的字串来替代整数。
　　以字串形式输入Ｎ，使用尽可能逼尽目标的贪心法来逐一删去其中Ｓ个数符，每一步总
是选择一个使得剩下的数最小的数符删去。至所以作出这样贪心的选择是因为删Ｓ个数符的全局最优
解，包含了删一个数符的子问题的最优解。
　　为了保证删１个数符后的数最小，我们按高位→低位的方向搜索递减区间。若不存在递
减区间，则删尾数符；否则删递减区间的首字符，这样形成了一个新数串。然后回到串首，
重复上述规则，删下一数符……依此类推，直至删除Ｓ个数符为止。
例如：N='178543',S=4,删数过程如下：
↓
　　　　　N='1 7 8 5 4 3' 　　　
↓
'1 7 5 4 3'
↓
'1 5 4 3'
↓
'1 4 3'
'1 3'
显然，按上述规则删去S个数符后，剩余N-S个数符组成的新数必定最小。

再如，例如：
N=175438, S=4
可以删去7,5,4,8,得到13。

#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<cmath>#include<vector>#include<map>#include<stack>#include<queue>#include<algorithm>using namespace std;#define max(a, b) a > b ? a : b#define min(a, b) a < b ? a : b#pragma comment(linker, "/STACK:102400000,102400000")string cmp(string &str, int n){string::iterator start;bool flag;for(int i = n; i > 0; --i){flag = 0;for(start = str.begin(); start < str.end() - 1; ++start){if(*start > *(start + 1)) // 每次删除第一个比下一个数字大的数{str.erase(start);flag = 1;break;}}if(!flag) //如果所有数字递增，则删除最后几个数字直接返回{str.erase(str.end() - i, str.end());break;}}return str;}int main(){//freopen("Input.txt", "r", stdin);int ncase, n;string str;scanf("%d", &ncase);while(ncase--){cin>>str;getchar();scanf("%d", &n);cout<<cmp(str, n)<<endl;}return 0;}