当前位置：首页 > news >正文

UVA11491 Erasing and Winning（单调队列/RMQ）

news 来源：原创 2024/4/27 23:24:53

题目链接

在这里插入图片描述
1.题目大意：给出一个n位整数，删除其中的d个数字，保证剩下的整数尽可能的大

2.第一眼没想到单调队列那种做法，反正题目意思明显就是每次保证取前n-m个（m递减），而且是这段序列中最大的元素，且位置越靠左越好，对于靠左的最大元素，如果遍历的话会使时间复杂度达到O(n²)，显然不可取的。于是emmm，预处理之后每次查询区间最值，这样的查询时间复杂度显然为O(n)

3.标答是利用单调队列的思想，在输入时就和前面已经输入的序列对比，在满足合法区间内取得每个数时，每次更新到前面的数大于等于当前输入的数，检查区间的合法性则直接向后更新，显然这样相当于在每次取数的序列里维护了一个降序的序列，且随时被覆盖更新，最后达到目的

RMQ：

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+10;


int a[maxn],dp[maxn][25];
int n,m;

void RMQ_init(){
    for(int i=1;i<=n;i++)
        dp[i][0]=a[i];
    for(int j=1;(1<<j)<=n;j++)
        for(int i=1;i+(1<<j-1)<=n;i++)
            dp[i][j]=max(dp[i][j-1],dp[i+(1<<j-1)][j-1]);
}

int query(int l,int r){
    int k=0;
    while((1<<(k+1))<=r-l+1) k++;
    return max(dp[l][k],dp[r-(1<<k)+1][k]);
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    string s;
    while(cin>>n>>m){
        if(!n && !m) break;
        cin>>s;
        for(int i=1,j=0;i<=n;i++,j++) a[i]=s[j]-'0';
        RMQ_init();
        int l=1,len=n-m;
        vector<int> ans;
        while(len){
            len--;
            int i=l,r=n-len;
            int now=query(l,r);
            while(a[i]<now) i++;
            ans.push_back(now);
            l=i+1;
        }
        for(int i=0;i<ans.size();i++) cout<<ans[i];
        cout<<endl;
    }
    return 0;
}

单调队列：

#include <iostream>
using namespace std;
const int maxn=2e5+10;

char s[maxn];

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,m;
    while(cin>>n>>m){
        if(!n && !m) break;
        int k=0;
        char c;
        for(int i=0;i<n;i++){
            cin>>c;
            while(k>0 && c>s[k] && k>i-m) k--;
            if(k+m<n) s[++k]=c;
        }
        s[++k]='\0';
        cout<<s+1<<endl;
    }
    return 0;
}