A Magic Lamp---hdu3183（链表删除| RMQ）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3183

给你一个长度<1000的数a，和m<len(a);

让把数a删除m个数字之后剩下的数组成的最小的数，不能改变剩下的树的顺序。。

每次删除数的时候都是删掉第一个比右边数大的数。

比如样例 178543  4

第一次删除第一个数的时候从左边找起。找到第一个a[i]>a[i+1]的数。删除8

17543

第二次一样的，删除7

1543

第三次删除5

143

第四次删除4

就得到13了。就是答案。

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

#define INF 0xfffffff
#define N 1050
struct node
{
    int pre, next, val;
}a[N];

char s[N];
int m;

int main()
{
    while(scanf("%s %d", s, &m)!=EOF)
    {
        memset(a, 0, sizeof(a));
        int n = strlen(s);
        a[0].next = 1; a[n+1].pre = n;
        for(int i=1; i<=n; i++)
        {
            a[i].pre = i-1;
            a[i].next = i+1;
            a[i].val = s[i-1]-'0';
        }
        int p=0;
        while(m--)
        {
            while(a[p].next!=n+1 && a[a[p].next].val >= a[p].val) p = a[p].next;
            a[a[p].next].pre = a[p].pre;
            a[a[p].pre].next = a[p].next;///删除结点p让p前后的相连接；
            p = a[p].pre;///为了不重复循环只需到前一结点即可；
        }
        p=0;
        while(a[p].next!=n+1 && a[p].val==0) p=a[p].next;
        if(p==n+1)///当到最后的时候也没找到不是0的数，说明剩下的全是0，输出0即可；
        {
            printf("0
");
            continue;
        }
        while(p!=n+1)
        {
            printf("%d", a[p].val);
            p=a[p].next;
        }
        printf("
");
    }
    return 0;
}