UVA11491 Erasing and Winning(单调队列/RMQ)
程序员文章站
2022-03-04 21:02:16
...
1.题目大意:给出一个n位整数,删除其中的d个数字,保证剩下的整数尽可能的大
2.第一眼没想到单调队列那种做法,反正题目意思明显就是每次保证取前n-m个(m递减),而且是这段序列中最大的元素,且位置越靠左越好,对于靠左的最大元素,如果遍历的话会使时间复杂度达到O(n2),显然不可取的。于是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;
}