Description
键盘输入一个高精度的正整数n(≤100位),去掉其中任意s个数字后剩下的数字按照原来的左右次序组成一个新的正整数。编程对给定的n与s,寻找一种方案,使得剩下的数字组成的新数最小。
Input
输入两个数字,分别为原始数n,要去掉的数字数s (s < n)。
Output
输出去掉s个数后最小的数
Sample
Input
178543 4
Output
13
很容易感觉是一道很简单贪心的题(就从大数开始删),但问题就在于高位数的删除权重要高于低位数 ,例如 6139 删除一个数,肯定是删除6而不是9
观察到这一点之后,我们再往深想一点,就是要维持在尽量删除左边数的情况下删除掉大数。
我们可以从左向右开始找,找一个大数,这个大数是什么样的? 一个要大于之前所有数的数。这样的数找到后,身后的数一定比它小
这样我们就从左到右,从升序开始找,找到第一个逆序对然后删除,然后继续找一个逆序对。知道删除的数量为s
#include<bits/stdc++.h> using namespace std; int main() { string a; int s,i; cin>>a>>s; while(s--) { i=0; while(a[i]<=a[i+1]) i++; a.erase(i,1); } int flag = 0; for(int i=0;i<a.size();i++) { if(a[i]=='0'&&i<a.size()-1&&flag == 0) continue; else { cout<<a[i]; flag = 1; } } }