双端队列:
1.头文件:#include<deque>
2.核心用法:
(定义) deque<int>q
用法 | 作用 |
---|---|
q.empty() | 直接判断是否为空 |
q.size() | 取得长度 |
q.back_pop() | 把队尾的元素弹出去 |
q.front_pop() | 把对头的元素弹出去 |
q.back_top() | 尾部元素的取值 |
q.front_top() | 头部元素的取值 |
本题:
[COCI2011-2012#4] KEKS
题目描述
给定正整数 N , K N,K N,K 和一个 N N N 位数,求在 N N N 位数中删除 K K K 位后剩下的数的最大值。
输入格式
第一行,两个整数 N , K N,K N,K。
第二行,一个 N N N 位整数。保证没有前导 0 0 0。
输出格式
输出剩下的数的最大值。
样例 #1
样例输入 #1
4 2
1924
样例输出 #1
94
样例 #2
样例输入 #2
7 3
1231234
样例输出 #2
3234
样例 #3
样例输入 #3
10 4
4177252841
样例输出 #3
775841
提示
【数据规模与约定】
- 对于 50 % 50\% 50% 的数据, N ≤ 1000 N \le 1000 N≤1000。
- 对于 100 % 100\% 100% 的数据, 1 ≤ K < N ≤ 5 × 1 0 5 1 \le K \lt N \le 5 \times 10^5 1≤K<N≤5×105。
【提示与说明】
题目译自 COCI 2011-2012 CONTEST #4 Task 3 KEKS。
本题分值按 COCI 原题设置,满分
100
100
100。
贪心思想:
以字符串的形式输入这个数,然后从前往后一次遍历,如果当前数比前面的数小就放进去,如果当前数比前面的大并且有删除机会,就把前面的删除
#include<iostream>
#include<cstring>
#include<string>
#include<deque>
using namespace std;
int n, m;
string s;
deque<char>q;//定义队列
int main()
{
cin >> n >> m >> s;//读入
for (int i = 0; i < s.size(); i++){
while (!q.empty() && m && s[i] - '0' > q.back()-'0')
//队列不空且有删除机会且当前数大于队尾元素
//记得要用while循环把能删的都删咯
{
m--;//机会减一
q.pop_back();//弹出去
}
q.push_back(s[i]);//否则加进来
}
while (q.size())
{
cout << q.front();
q.pop_front();
}
return 0;
}