学步园

一、试 题
    键盘输入一个高精度的正整数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;
}