hdu 3183 A Magic Lamp RMQ ST 坐标最小值

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

题目大意：

从给定的串中挑出来m个数使得剩余的数字最小，串的序列不能改变

思路：

将问题转化为求在n个数中挑选n-m个数，使之最小。假设最极端的情况，所有最大的数字都在左侧，占据了m个位置，那么我们需要挑选的最小的数字的第一位就是在m+1位上。依次类推，第二位在m+2位上，最后一位也就在原串的最后一位上。反过来，假设最大的数字都在右侧，占了m个位置。那么我们需要挑选的最小数字的最后一位就是在n-m位上，倒数第二位在n-m-1位上，最终最后一位就是在第一位上。至此，可以得到我们挑选最小数的第一位的取值范围就是[1,m+1]。类比可得，第二位取值范围[2,m+2]，...。假设我们此时已经求出了第一位所在的位置x，那么第二位数字的范围就可以进一步缩小为[x+1,m+2]，依次我们可以求出全部的数字。同时要注意，ST表中保存的是该段区间最小值的下标。
ST在线预处理O(nlogn) 查询O(1) 运行时间：15ms
这道题注意的细节有很多，写了很久才敢提交还是WA了3发。/(ㄒoㄒ)/~~要注意题中说n不会大于串的长度是不成立的，要来特判

代码：

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <math.h>

using namespace std;

const int maxn = 1005;

int minindex[maxn][10],data[maxn],res[maxn];

inline void init(int len) {

    for(int i=1; i<=len; ++i) minindex[i][0]=i;

    for(int j=1; j<=10; ++j) {

        for(int i=1; i<=len; ++i) {

            if((i+(1<<j)-1)<=len) {

                int t1=minindex[i][j-1],t2=minindex[i+(1<<(j-1))][j-1];

                if(data[t1]<=data[t2]) minindex[i][j]=t1;

                else minindex[i][j]=t2;

            }

        }

    }

}

inline int ask(int l, int r) {

    int k=31-__builtin_clz(r-l+1);

    int t1=minindex[l][k],t2=minindex[r-(1<<k)+1][k];

    if(data[t1]<=data[t2]) return t1;

    else return t2;

}

int main() {

    char s[1005];

    int n,len,l,r,ip1,ip2;

    while(~scanf("%s %d",s,&n)) {

        memset(minindex,0,sizeof(minindex));

        len=strlen(s);

        for(int i=0; i<len; ++i) {

            data[i+1]=s[i]-'0';

        }

        if(n>=len) {

            printf("0\n");

            continue;

        }

        init(len);

        len=len-n;

        l=1,r=n+1;

        ip2=1;

        for(int i=1; i<=len; ++i) {

            ip1=ask(l,r);

            res[ip2]=data[ip1];

            ++ip2;

            l=ip1+1;

            ++r;

        }

        ip2--;

        for(l=1; l<=ip2; ++l) {

            if(res[l]) break;

        }

        if(l>ip2) {

            printf("0\n");

            continue;

        }

        for(int i=l; i<=ip2; ++i) printf("%d",res[i]);

        printf("\n");

    }

    return 0;

}

巴特西

hdu 3183 A Magic Lamp RMQ ST 坐标最小值

hdu 3183 A Magic Lamp RMQ ST 坐标最小值

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

题目大意：

思路：

代码：

最新文章

热门文章