CF1237D Balanced Playlist 题解

Unnamed114514 · 2021-12-28 21:36:18 · 题解

对于本题，我们可以先考虑无解的情况：在多次遍历后，最大值和最小值都已遍历，此时若最小值和最大值都不满足题目中的条件的话，我们就发现它会一直循环下去。

在判断了无解之后，我们可以构建一个单调递减队列，此时队首存储的是当前遍历到的最大值，队尾为当前遍历到的最小值，此时我们已经保证有解了。如果我们的队首和队尾已经满足有解，记录答案为 k。

此时，我们可以发现：有些答案有解，有些答案还是空着的。此时我们需要填充它。设 i 表示当前需要填充的答案，则对于后面的第一个有答案的位置 j，我们只需要先从 i\to j，再得到 j 的答案 ans_j，答案就是 j-i+ans_j。此时我们可以用递推优化：假设 k 还暂时没有解，k+1 此时已经有解，从刚刚推出的公式可以发现：ans_k\gets ans_k+(k+1)-k=ans_k+1。

对于数组大小，我们可以开到三倍：因为我们至少要在遍历最大值之后再遍历一次最小值，于是我们就只能先遍历一层循环，此时若最小值比最大值先遍历到，我们还需要再遍历一次，才能满足在最大值之后遍历最小值。

时空复杂度均为 O(3n)。

AC Code:

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+5;
inline int read(){
    int res=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
        ch=getchar();
    while(ch>='0'&&ch<='9'){
        res=(res<<1)+(res<<3)+(ch^'0');
        ch=getchar();
    }
    return res;
}
int n,a[maxn],mx,ix=1e9+1,q[maxn],l,r,ans[maxn];
int main(){
    int n=read();
    for(int i=1;i<=n;++i)
        a[i+n*2]=a[i+n]=a[i]=read(),mx=max(mx,a[i]),ix=min(ix,a[i]);
    if(mx<=(ix<<1)){
        for(int i=1;i<=n;++i)
            printf("-1 ");
        return 0;
    }//剪枝：唯一的无解情况——最大值小于等于最小值的两倍
    for(int i=1;i<=3*n;++i){
        while(l<=r&&a[q[l]]>(a[i]<<1))
            ans[q[l]]=i-q[l],++l;
        while(l<=r&&a[q[r]]<a[i])
            --r;
        q[++r]=i;
    }
    for(int i=n*3;i;--i)
        if(!ans[i])
            ans[i]=ans[i+1]+1;
    for(int i=1;i<=n;++i)
        printf("%d ",ans[i]);
    return 0;
}