NYOJ448 尋找最大數

原題目：點選打開連結 描述

請在整數 n 中删除m個數字, 使得餘下的數字按原次序組成的新數最大，

比如當n=92081346718538，m=10時，則新的最大數是9888

 輸入

第一行輸入一個正整數T，表示有T組測試資料

每組測試資料占一行，每行有兩個數n,m（n可能是一個很大的整數，但其位數不超過100位，并且保證資料首位非0，m小于整數n的位數）

輸出

每組測試資料的輸出占一行，輸出剩餘的數字按原次序組成的最大新數

樣例輸入

2
92081346718538 10
1008908 5      

樣例輸出

9888
98      

解題思路：貪心型題目，n個數剔除m個，所剩下的數按原序最大。注意題目的要求。是以可以轉換為從n個數中取出k=n-m個，組成的數最大。取法為：第一次可以從第一位開始取，可以選擇的範圍應該是1至n-k+1 ，取到n-k+1的理由是第n-k+1位（包括該位）的右邊隻有k個數，是以這是個右邊界。這個細心點分析下就行。

#include <iostream>
#include <string.h>
using namespace std;
char c[101];
int main(){
	int T,n,m,k;
	cin>>T;
	while(T--){
		cin>>c>>m;
		n=strlen(c);
		k=n-m;//将問題轉化為取出k=n-m為數，使其最大 
		int begin =0,end=n-k,index=0,num,Max=-1; 
		for(int i=0;i<k;i++){
			for(int j=begin ;j<=end;j++){//周遊數組，注意開始和結束位置的改變 
				num=c[j]-'0';
				if(num>Max){//不要寫>=,因為最大數字有多個，我們去最左邊的那個 
					Max=num;
					index=j;
				}	
			}
			cout<<Max;
			Max=-1;
			begin=index+1;//注意是index+1； 
			end++;
		}
		cout<<endl;	
	}
	return 0;
}