Codeforces 1237D. Balanced Playlist

首先显然的，如果一个位置开始播放了两圈还没结束，那么就永远不会结束

先考虑位置 $1$ 开始播放，用一个 $multisetset$ 维护一下当前听的所有歌，直到某一首歌 $r$ 不合法了就停止，此时播放的区间即为位置 $1$ 开始的答案

然后考虑从位置 $2$ 开始播放时和从位置 $1$ 开始播放有什么变化，显然播放的歌曲一定可以到 $r$ （反证法容易证明），并且 $multiset$ 里少了一首位置 $1$ 的歌

那么直接把 $multiset$ 更新一下，然后继续模拟过程直到下一个不合法，然后又可以算出答案

这样一直算下去即可求出所有答案

均摊复杂度 $O(n \log n)$，注意要把听歌的序列延长 $3$ 倍而不是两倍（看样例 $2$ 就知道了）

数组也要开 $3$ 倍！（如果你像我一样不小心开了两倍，那么结果就是通过 $\text{pretest}$ 然后 $WA$ 在 $\text{system test}$）

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<set>

using namespace std;

typedef long long ll;

inline int read()

{

    int x=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=3e5+;

int n,n3,ans[N];

int A[N];

multiset <int> S;

int main()

{

    n=read(),n3=n*;

    for(int i=;i<=n;i++) A[n*+i]=A[n+i]=A[i]=read();

    int r=;

    for(int i=;i<=n;i++)

    {

        while(r<=n3)

        {

            if(S.size())

            {

                int p=*S.rbegin();

                if(A[r]<p/ || (A[r]==p/ && p&))

                    break;

            }

            S.insert(A[r]); r++;

        }

        ans[i]= r<=n3 ? r-i : -; S.erase(S.find(A[i]));

    }

    for(int i=;i<=n;i++) printf("%d ",ans[i]);

    puts(""); return ;

}

巴特西

Codeforces 1237D. Balanced Playlist

最新文章

热门文章