uva 11491 Erasing and Winning 獎品的價值 (單調隊列)

解題關鍵在于，首先要發現性質，題目要求在n個有序數字中，選取n-d個數字，使得剩下組成的數最大。

先考慮選取第一位：越大越好，越靠左越好。

解法：維護一個單調遞減的隊列。

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;

#define all(x) (x).begin(), (x).end()
#define for0(a, n) for (int (a) = 0; (a) < (n); (a)++)
#define for1(a, n) for (int (a) = 1; (a) <= (n); (a)++)
typedef long long ll;
typedef pair<int, int> pii;
const int INF =0x3f3f3f3f;
const int maxn= 100000  ;

int n,d,V;
char s[maxn+10];
bool vis[maxn+10];
int q[maxn+10];
int main()
{
    while(~scanf("%d%d",&n,&d)&&(n||d))
    {
        scanf("%s",s+1);
        V=n-d;
        memset(vis,0,(n+1)*sizeof vis[0]);
        int rear=1,front=1;
        for(int i=1;i<=n-V;i++ )
        {
            while(rear-front>0&&s[q[rear-1]]<s[i]  ) rear--;
            q[rear++]=i;
        }
        for(int i=n-V+1;i<=n;i++)
        {
            while(rear-front>0&&s[q[rear-1]]<s[i]  ) rear--;
            q[rear++]=i;

            int x=q[front];
            vis[x]=1;
            front++;
        }
        for(int i=1;i<=n;i++) if(vis[i])
        {
            putchar(s[i]);
        }
        putchar('\n');

    }

   return 0;
}