hdu 3183 A Magic Lamp（RMQ）

zgdy

　　题意：将一个给定的数删除m位，求剩下的数的最小值
　　分析：用RMQ，假设原来数字的长度为n，每次从一个区间里面取出一个最小值，取n-m即可


View Code


#include<iostream>
#include<algorithm>
#include<string.h>
#include<math.h>
using namespace std;
int n,dp[1010][20];
char B[1010];
void init_RMQ()
{
    memset(dp,0,sizeof(dp));
    for(int i=0;i<n;i++)
        dp[0]=i;
    for(int j=1;j<log((double)(n))/log(2.0);j++)
    {
        int limit=n+1-(1<<j);
        for(int i=0;i<limit;i++)
        {
            int x=dp[j-1];
            int y=dp[i+(1<<(j-1))][j-1];
            dp[j]=B[x]<=B[y]?x:y;
        }
    }
}
int RMQ(int a,int b)
{
    int k=(int)(log((double)(b-a+1))/log(2.0));
    int x=dp[a][k];
    int y=dp[b+1-(1<<k)][k];
    return B[x]<=B[y]?x:y;
}
int main()
{
    int m,l,r;
    char ans[1000];
    while(scanf("%s %d",B,&m)==2)
    {
        n=strlen(B);
        init_RMQ();
        m= n-m;
        l=0;
        r=n-m;
        int t=m,len1=0;
        while(t--)
        {
            l=RMQ(l,r);
            r++;
            ans[len1++]=B[l];
            l++;
            //求出每一次取值的左右区间
        }
        ans[len1]='\0';
        int flag=1;
        for(int i=0;i<len1;i++)
        {
            if(flag && ans=='0')
                continue;
            flag=0;
            printf("%c",ans);
        }
        if(flag)
        puts("0");
        else puts("");
    }
    return 0;
}