P10059 Choose
white_tiger_yyyy
·
·
题解
博客食用更佳。
正篇开始
考虑题目中很重要的一句话：
- 记这 k 个子序列中极差的最小值为 X，你需要求出 X 的最大值。
很明显，要求最小值最大，显然二分答案。那么问题来了，二分什么呢？
现在有两个选择：二分极差、二分长度。
很明显，前者可以一次性都算出来，但是十分麻烦，无从下手；后者只能算出长度，但是二分思路很简单。这个时候，我们就需要发现一些性质了。
性质1：区间 [l,r] 的子区间求出的极差绝对没有该区间大。
性质2：所有长度为 l 的区间，都可以被长为 l+1 的区间包含。
根据这两个性质，显而易见就可以推导出结论：
结论：区间长度越长，答案或更优，或不变。
这样，一个贪心求极差的方法显然出现：直接枚举所有长度为 n-k+1 的区间，求出这些区间的极差最小值 X'，第一个答案即为 X'。
既然我们可以求出极差，那么我们就不需要二分极差，因此只能二分长度。但是问题接踵而至：如何快速计算区间极差呢？
解决这个问题，我们需要知道一件事情：区间极差=区间最大值-区间最小值。
问题转化为：如何快速求出静态区间最大/最小值？
用线段树自然可以，但是时间复杂度不如 RMQ。现在，我们只需要解决 \operatorname{check} 函数即可。
二分长度，当该长度的区间中，有大于等于 $k$ 个大于 $X$，返回 $1$，否则返回 $0$。
现在我们会发现，使用线段树，时间复杂度会多一个 $\log$，而根据分析，原先的时间复杂度为 $O(n\log_2n)$，已经容不得 $n\log^2_2n$ 了。
空间复杂度最大是 RMQ，空间复杂度 $O(n\log_2n)$，最好预处理 $\log$。
---
标程
```cpp
#include<bits/stdc++.h>
#define N 100005
#define M 1000005
using namespace std;
int t,n,k,a[N],mx[M],mn[N],ans1;
int lg[N],f[N][20],dp[N][20];
void build(){
for(int i=1;i<=100000;i++)
for(int j=1;j<17;j++) f[i][j]=-1e9-1;
for(int i=1;i<=100000;i++)
for(int j=1;j<17;j++) dp[i][j]=1e9+1;
for(int i=1;i<=n;i++) f[i][0]=dp[i][0]=a[i];
for(int j=1;j<17;j++)
for(int i=1;i+(1<<j)-1<=n;i++){
f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
}int qmax(int l,int r){
int zjy=lg[r-l+1];
return max(f[l][zjy],f[r-(1<<zjy)+1][zjy]);
}int qmin(int l,int r){
int zjy=lg[r-l+1];
return min(dp[l][zjy],dp[r-(1<<zjy)+1][zjy]);
}int check(int x){
int sum=0;
for(int i=1;i<=n-x+1;i++){
int lyh=qmax(i,i+x-1);
int zjy=qmin(i,i+x-1);
if(lyh-zjy>=ans1) sum++;
}return sum>=k;
}int main(){
for(int i=1;i<N;i++) lg[i]=log2(i);
cin>>t;while(t--){
cin>>n>>k;ans1=2e9+1;
for(int i=1;i<=n;i++) cin>>a[i];
build();
for(int i=1;i<=k;i++)
ans1=min(ans1,qmax(i,n-k+i)-qmin(i,n-k+i));
cout<<ans1<<" ";int l=1,r=n-k+1,ans2;
while(l<=r){
int mid=(l+r)/2;
if(!check(mid)) l=mid+1;
else r=mid-1,ans2=mid;
}cout<<ans2<<"\n";
}return 0;
}
```
---
赛后还有加强版，这会主要卡空间，所以无法支付 RMQ 的空间。
考虑单调队列。由于本题所需要的最大最小值，实际上是滑动窗口板子，所以可以将空间复杂度压缩至 $O(n)$。代码就不写了，留给大家探索。