整数去位

http://218.5.5.242:9018/JudgeOnline/problem.php?id=1134

题目描述

键盘输入一个高精度的正整数N，去掉其中任意M个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的N和M寻找一种方案使得剩下的数字组成的新数最小。输出组成的新的正整数。
输入数据均不需判错。如果去掉了某几个位后得到的新整数开头为0，保留0。
输入：
505
1
输出：
05

输入

第一行为高精度正整数N（N的长度不超过10^6位）
第二行为M（0<=M<=N的长度）

输出

去掉M位后的最小新数。

样例输入

82386782
3

样例输出

23672

 就是贪心，每次直接扫i-i+k，如果这里面有比i小的数j，就把那个数前面的全部去掉k-=j-i，然后再以这个数为起点，继续扫i-i+k的数
但是这题这样搞肯定tle的，如果是全上升序列10^6
所以我就把这个过程简化成，先求出一个数组中每个数后面最近比它小的那个数的位置，然后就可以不用扫了
最后就这样

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
#define X first
#define Y second
#define mp(a,b) make_pair(a,b)
#define pb push_back
#define sd(x) scanf("%d",&(x))
#define Pi acos(-1.0)
#define sf(x) scanf("%lf",&(x))
#define ss(x) scanf("%s",(x))
#define maxn 50005
const int inf=0x3f3f3f3f;
const ll mod=1000000007;
char a[1000005];
int cnt[1000005];
int main()
{
#ifdef local
    freopen("in","r",stdin);
    //freopen("out","w",stdout);
    int _time=clock();
#endif
    int k;
    int l=0;
    scanf("%s",a);
    scanf("%d",&k);
    l=strlen(a);
    cnt[l]=inf;
    for(int i=l-1;i>=0;i--)
    {
        if(a[i]>a[i+1])cnt[i]=i+1;
        else
        {
            int t=i+1;
            while(a[i]<=a[t]&&a[t]!=inf)
            {
                t=cnt[t];
            }
            cnt[i]=t;
        }
    }
    int i=0;
    bool flag=0;
    while(k>0)
    {
        if(cnt[i]-i<=k)
        {
            k-=cnt[i]-i;
            i=cnt[i];
            flag=1;
        }
        if(flag==0)
            putchar(a[i++]);
        else
            flag=0;
    }
    while(i<l)
        putchar(a[i++]);
#ifdef local
    printf("time: %d
",int(clock()-_time));
#endif
}
/**************************************************************
    Problem: 1134
    User: caobao
    Language: C++
    Result: 正确
    Time:48 ms
    Memory:6368 kb
****************************************************************/