COJ 删除数字

试题描述

输入正整数N和M，在N中删除掉M位，能留下的最大整数是多少？

输入

正整数N和M

输出

留下的最大整数

输入示例

233390323 5

输出示例

9323

其他说明

1<=N<=10^1000 1<=M<=1000

N的长度比较小，胡搞就行了。

那么如果1<=N<=10^1000000呢？

考虑当前最后保留的位置是cur，还要删m个字符，那么下一个要删的区间应是[cur+1,cur+m+1]，那么我们要设计一个数据结构快速找到区间最大值。

这显然是个滑动窗口，用单调队列做做就行了（<--WZJ这蒟蒻竟然没看出来写了线段树）。注意这组数据636546796 8要输出9，即如果最后还没删够要输出前n-m个得到的字符。

#include<cstdio>
#include<cctype>
#include<ctime>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define ren for(int i=first[x];i!=-1;i=next[i])
using namespace std;
inline int read() {
    int x=,f=;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
    for(;isdigit(c);c=getchar()) x=x*+c-'';
    return x*f;
}
char s[],q[];
int maxv[];
void build(int o,int l,int r) {
    if(l==r) maxv[o]=l;
    else {
        int mid=l+r>>,lc=o<<,rc=lc|;
        build(lc,l,mid);build(rc,mid+,r);
        if(s[maxv[lc]]>=s[maxv[rc]]) maxv[o]=maxv[lc];
        else maxv[o]=maxv[rc];
    }
}
int ql,qr;
int query(int o,int l,int r) {
    if(ql<=l&&r<=qr) return maxv[o];
    int mid=l+r>>,lc=o<<,rc=lc|;
    if(qr<=mid) return query(lc,l,mid);
    if(ql>mid) return query(rc,mid+,r);
    int ans1=query(lc,l,mid),ans2=query(rc,mid+,r);
    return s[ans1]>=s[ans2]?ans1:ans2;
}
int main() {
    int m,cnt=,t;
    scanf("%s%d",s+,&m);t=m;
    int n=strlen(s+),cur=;
    build(,,n);
    while(cur<n) {
        ql=cur+;qr=min(cur+m+,n);
        int next=query(,,n);
        m-=next-cur-;cur=next;
        q[++cnt]=s[cur];if(m<=) break;
    }
    if(m) rep(i,,n-t) putchar(q[i]);
    else {
         printf("%s",q+);
         rep(i,cur+,n) putchar(s[i]);
    }
    return ;
}