P8082 [COCI2011-2012#4] KEKS[贪心思想加双端队列详解]

双端队列:
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$ 位数，求在 $N$ 位数中删除 $K$ 位后剩下的数的最大值。

输入格式

第一行，两个整数 $N, K$ 。

第二行，一个 $N$ 位整数。保证没有前导 $0$ 。

输出格式

输出剩下的数的最大值。

样例 #1

样例输入 #1

4 2
1924

样例输出 #1

样例 #2

样例输入 #2

7 3
1231234

样例输出 #2

样例 #3

样例输入 #3

10 4
4177252841

样例输出 #3

提示

【数据规模与约定】

对于 $50\%$ 的数据， $\le 1000$ 。
对于 $100\%$ 的数据， $\le K \lt N \le 5 \times 10^5$ 。

【提示与说明】

题目译自 COCI 2011-2012 CONTEST #4 Task 3 KEKS。

本题分值按 COCI 原题设置，满分 $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;
 }