Codeforces 1237D Balanced Playlist 题解

发表于 | 更新于 | 阅读次数：
本文字数： 1.1k 字 | 阅读时长 ≈ 4 分钟

题意简述

n首歌循环播放。每首歌有一个欢乐值。播放到一首歌，如果这首歌的欢乐值的两倍小于放过的最大值，则停止。对于每首歌，求出从这首歌开始播放，能放几首歌。n<=1e5。

思路框架

如果全局最小值的两倍>=全局最大值，直接全部输出-1。

数组开三倍。维护一个单调递减的单调队列。现在考虑到$i$，先把$a[i]$入队列。如果$a[i]$两倍小于队首$H$，记录$ans[H]=i-H$，弹出队首。对于没有处理过的位置$i$，直接ans[i]=ans[i+1]+1。输出1~n位置的答案。

具体思路

由于是循环的问题，我们考虑把数组开两倍。但是看到样例二，手动模拟一下，发现这不够，要三倍。

开始分析。显然，$i$位置能播放到的位置肯定<=$i+1$能放到的位置。比如这组数据：

1
2
15
58 37 28 74 28 41 50 34 72 79 45 42 94 54 39

我们计算每个位置能放到的位置，得到这样一个数组：

1
3 5 5 5 15 15 15 15 15 15 15 15 15 18 18

（小数据，可以手做做看或者模拟）

设这个数组为$pos$。题目让我们求的就是$pos[i]-i$，并输出。设题目求的是$ans$数组。
那么我们考虑求这个$pos$。如果不是在“转折点”的时候，应该满足$ans[i]=ans[i+1]+1$。
所以我们现在就是要求这些转折点位置的答案。别的位置就直接$ans[i]=ans[i+1]+1$。

求转折点位置及答案

思考：为什么会有“转折”？

比如说第$i$个位置和第$i+1$个位置不一样。那么肯定是因为$i$位置更新了最大值，让最大值变大了，更加容易满足条件，所以答案减少。

能更新最大值的位置，就是转折点。我们用一个单调队列维护即珂（队列里面维护下标）。

入队列的条件

如果有一个元素A比另一个元素B排在后面，然后A还比B大，那么B无论如何也不会更新最大值了。因为，只要能考虑到B，就肯定能考虑到A，而且A还比你大。所以我们的队列，如果新的队尾大于原来的队尾，那么就弹出原来的队尾。换句话说，就是维护一个单调递减的队列。

出队列的条件

如果当前考虑的$i$，满足$a[i]$两倍小于队首$H$，那么如果从$H$开始播放，肯定播放到$i$就停止了，后面就不会再有影响。所以如果发生了这样的情况，就记录队首的答案，并且把它弹出去。

转折点篇 完

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

#include <bits/stdc++.h>using namespace std;
namespace Flandre_Scarlet
{
    #define N 355555
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)
    #define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
    #define p_b push_back
    #define sz(a) ((int)a.size())
    #define iter(a,p) (a.begin()+p)

    void R1(int &x)
    {
        x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        x=(f==1)?x:-x;
    }
    int n,a[N];
    void Input()
    {
        R1(n);F(i,1,n) R1(a[i]),a[i+n]=a[i+2*n]=a[i];
    }
    int Q[N],head,tail;
    int ans[N];
    void Soviet()
    {
        int Max=*max_element(a+1,a+n+1),Min=*min_element(a+1,a+n+1);
        if (Min*2>=Max) 
        {
            F(i,1,n) printf("-1%c"," \n"[i==n]);
            return;
        }//特判-1

        head=0,tail=1;
        F(i,1,3*n)
        {
            while(head<=tail and a[Q[tail]]<a[i]) --tail;
            Q[++tail]=i; //入队列

            while(head<=tail and a[Q[head]]>2*a[i])  
            {
                ans[Q[head]]=i-Q[head]; //到i为止，但是题目要求输出的是pos[i]-i，所以干脆直接令答案为i-Q[head]
                ++head;
            }
        }
        D(i,3*n,1)
        {
            if (ans[i]==0) ans[i]=ans[i+1]+1; //直接继承
        }
        F(i,1,n) printf("%d\n",ans[i]);
    }

    #define Flan void
    Flan IsMyWife()
    {
        Input();
        Soviet();
    }
}
int main(){
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}
w