描述
Given an N-digit number, you should remove K digits and make the new integer as large as possible.
输入
- The first line has two integers N and K (1 K<N500000).
- The next line has a N-digit number with no leading zero.
输出
Output the largest possible integers by removing K digits.
样例输入
4 2
2835
样例输出
85
题意:
给定一个 n 位数字, 删去 k 个数字使之最大.
思路:
利用单调栈进行贪心, 即保持栈为降序的过程中, 记录删除数字的个数, 删到 k 个即止.
- #include<bits/stdc++.h>
- #define MAX 500005
- using namespace std;
- int main()
- {
- char st[MAX],ch;
- int top=-1,n,k,i;
- cin>>n>>k;
- st[++top]='9';
- getchar();
- for(i=0;i<n;i++)
- {
- ch=getchar();
- while(ch>st[top]&&k)
- {
- top--;
- k--;
- }
- st[++top]=ch;
- }
- printf("%s",st+1);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2759687.html