3183 RMQ / 贪心（坑成。。）

时间：2022-08-15 08:52:28

题意：删去m个数，使剩下的数组成的数最小

题解 ：贪心 ， RMQ

RMQ解法，建st表找，用rmq找最小值的下标，注意点 ，因为最小值是区间最右最小值，所以应该改成 <= 而不是<

minpos[i][j] = b[minpos[i][j - ]] <= b[minpos[i + ( << (j - ))][j - ]] ? minpos[i][j - ] : minpos[i + ( << (j - ))][j - ];

且rmq查询也要同步

#include<iostream>

#include<cstdio>

#include<string>

#include<cmath>

#include<cstring>

using namespace std;

#define MAXN 20000 +9

#define MAXE 22

int h[MAXN],minpos[MAXN][MAXE];

int F_Min[MAXN][MAXE];

int N,Q;

int L,R;

// void RMQ_ST(){

//     for(int i=1;i<=N;i++){

//         mmax[i][0]=h[i];

//     }

//     int end_j=log(N+0.0)/log(2.0);

//     int end_i;

//     for(int j=1;j<=end_j;j++){

//         end_i=N+1-(1<<j);

//         for(int i=1;i<=end_i;i++){

//             //mmax[i][j]=max(mmax[i][j-1],mmax[i+(1<<(j-1))][j-1]);

//            mmin[i][j]=min(mmin[i][j-1],mmin[i+(1<<(j-1))][j-1]);

//         }

//     }

// }

// int QueryMin(int L,int R){

//     int k=log(R-L+1.0)/log(2.0);

//     return min(mmin[L][k],mmin[R-(1<<k)+1][k]);

// }

void RMQ_pos_init(int n, int b[]){

    int i, j;

    for (i = ; i <= n; i++) {

       // maxpos[i][0] = i;

        minpos[i][] = i;

    }

    for (j = ; ( << j) <= n; j++)

        for (i = ; i + ( << j) -  <= n; i++){

            minpos[i][j] = b[minpos[i][j - ]] <= b[minpos[i + ( << (j - ))][j - ]] ? minpos[i][j - ] : minpos[i + ( << (j - ))][j - ];

            //maxpos[i][j] = b[maxpos[i][j - 1]] > b[maxpos[i + (1 << (j - 1))][j - 1]] ? maxpos[i][j - 1] : maxpos[i + (1 << (j - 1))][j - 1];

        }

}

int RMQ_pos_min(int s, int v, int b[]){

    int k = (int)(log((v - s + )*1.0) / log(2.0));

    return b[minpos[s][k]] <= b[minpos[v - ( << k) + ][k]] ? minpos[s][k] : minpos[v - ( << k) + ][k];

}

char str[+ ];

int ans[ + ];

int main(int argc, char const *argv[])

{

    int n;

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

        int len = strlen(str);

        int l = , r = n + ;

        int m = len - n ;

        int sum = ;

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

            h[i + ] = str[i] - '';

        }

       // for(int i = 1;i )

        RMQ_pos_init(len,h);

        while(m--){

            int i = l ;

            int size = l ;

            // for(;i <= r;i++){

            //     if((str[i] - '0') < (str[size] - '0')) size = i;

            // }

            //cout << l << " " << r << endl;

            size = RMQ_pos_min(l,r,h);

            //cout << size << endl;

            ans[sum++] = h[size];

            l = size + ;

            r++;

        }

        int i = ;

        while(ans[i] ==  && i < sum) i++;

        if(i == sum) printf("");

        else

        // for(auto au : ans){

        //     printf("%d",ans );

        // }

        for(;i < sum; i++) printf("%d",ans[i]);

        printf("\n");

    }

    return ;

}

RMQ

贪心解法

删除m个数字，相当于在里面从左往右取n-m个数字；所得数最小，也就是每次取得数字尽量小。那么，取得的第一个数字一定在区间[0,m]内，为什么呢？因为除了第一个数之外还要取n-m-1个数字，所以区间右边界最大只能是m，每次在区间里找最小的那个数(尽量靠左)；依次类推，假设第一个数字取得的下标是index1，那么，第二个数字一定是在[index1+1,m+1]内取得；依次类推下去，右边界每次加1。当选取到了n-m个数字之后，也就找到了答案了~

#include<iostream>

#include<cstdio>

#include<string>

#include<cmath>

#include<cstring>

using namespace std;

#define MAXN 200000 +9

#define MAXE 22

int h[MAXN],mmax[MAXN][MAXE];

int N,Q;

int L,R;

void RMQ_ST(){

    for(int i=;i<=N;i++){

        mmax[i][]=h[i];

    }

    int end_j=log(N+0.0)/log(2.0);

    int end_i;

    for(int j=;j<=end_j;j++){

        end_i=N+-(<<j);

        for(int i=;i<=end_i;i++){

            mmax[i][j]=max(mmax[i][j-],mmax[i+(<<(j-))][j-]);

           // mmin[i][j]=min(mmin[i][j-1],mmin[i+(1<<(j-1))][j-1]);

        }

    }

}

int QueryMax(int L,int R){

    int k=log(R-L+1.0)/log(2.0);

    return max(mmax[L][k],mmax[R-(<<k)+][k]);

}

char str[+ ];

int ans[ + ];

int main(int argc, char const *argv[])

{

    int n;

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

        int len = strlen(str);

        int l = , r = n;

        int m = len - n;

        int sum = ;

        while(m--){

            int i = l;

            int size = l;

            for(;i <= r;i++){

                if((str[i] - '') < (str[size] - '')) size = i;

            }

            ans[sum++] = str[size] - '';

            l = size + ;

            r++;

        }

        int i = ;

        while(ans[i] ==  && i < sum) i++;

        if(i == sum) printf("");

        else

        // for(auto au : ans){

        //     printf("%d",ans );

        // }

        for(;i < sum; i++) printf("%d",ans[i]);

        printf("\n");

    }

    return ;

}

贪心

相关文章