题目描述

难度分:$2000$

输入$n(2 \leq n \leq 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 10^9)$。

0x3F的播放列表中有$n$首歌，列表中的第$i$首歌的好听度为$a[i]$。这$n$首歌按照【列表循环】模式播放。播放完第$n$首歌，就会播放第$1$首歌。如果0x3F听到一首歌，发现它的好听度$\times 2$小于之前听到的最好听的歌，那么0x3F就会立刻停止播放。

输出$n$个数，其中第$i$个数等于：从播放列表中的第$i$首歌开始听，到停止播放时，完整播放的歌曲数目（停止播放时的那首歌不算）。

对于同一首歌，如果它被完整播放$x$次，就会统计$x$次。见示例$2$。如果可以无限循环，输出$-1$。

输入样例$1$

4
11 5 2 7

输出样例$1$

1 1 3 2

输入样例$2$

4
3 2 5 3

输出样例$2$

5 4 3 6

输入样例$3$

3
4 3 6

输出样例$3$

-1 -1 -1

算法

单调队列

播放列表$playlist$是循环的，不是很好处理，因此第一步就是破环成链，将数组$a$复制两份在后面，让数组$a$的有效范围从$[1,n]$变成$[1,3n]$。至于为什么是$3$倍？其实我在做的时候没有考虑太清楚，本来用的$2$倍，发现样例$2$的最后一个位置$i=n$就得不到正确答案，然后经过分析确定$3$倍就足矣得到正确答案。

然后用两个指针$i=1$和$j=i+1$开始遍历播放列表，如果$j \leq 3n$且$a[j] \times 2 \geq mx$（其中$mx$是子数组$[i,j)$中的元素最大值），就让$j$右移。此时我们发现这就是一个滑动窗口维护最值的问题，用一个单调队列$q$来维护最大值对应的索引。

退出循环就意味着当前需要结算$i$的答案，有以下两种情况：

1. 如果$j \leq 3n$，说明退出循环的条件是$a[j] \times 2 \lt mx$，存在有效解，$[i,j)$中的歌曲都是能完整播放的，答案为$j-i$。
2. 否则说明后面循环回到$i$位置也找不到一个满足$a[j] \times 2 \lt mx$的终止位置$j$，可以无限循环，答案为$-1$。

如果队列$q$的头部就是$i$，需要将队首弹出，然后考虑下一个位置，$i=i+1$自增。这里有一个很关键的性质，当起点为$i+1$时，它的终止播放位置$j’$肯定不会在起点为$i$时的终止播放位置$j$前面（即$j’ \geq j$），因此$j$指针也和$i$一样是不回退的，整个算法可以在线性时间复杂度下执行完成。

复杂度分析

时间复杂度

遍历$i \in [1,n]$，$j \in [1,3n]$，两个指针都是前进不后退，因此线性时间就可以求得每个$i$的答案。整个算法的时间复杂度为$O(n)$。

空间复杂度

除了输入的$a$数组，空间消耗就是单调队列对应的双端队列$q$，$i \in [1,3n]$的每个元素最多进一次队列出一次队列，在最差情况下额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 300010;
int n, a[N];

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        a[i + n] = a[i + 2*n] = a[i];
    }
    deque<int> q;
    q.push_back(1);
    for(int i = 1, j = i + 1; i <= n; i++) {
        while(j <= 3*n && a[j]*2 >= a[q.size()? q.front(): 0]) {
            while(q.size() && a[q.back()] < a[j]) q.pop_back();
            q.push_back(j++);
        }
        if(j <= 3*n) printf("%d ", j - i);
        else printf("%d ", -1);
        if(q.size() && q.front() == i) q.pop_front();
    }
    return 0;
}