codeforces-1237D - Balanced Playlist
链接：https://codeforces.com/problemset/problem/1237/D
题目
Your favorite music streaming platform has formed a perfectly balanced playlist exclusively for you. The playlist consists of n tracks numbered from 1 to n. The playlist is automatic and cyclic: whenever track i finishes playing, track i+1 starts playing automatically; after track n goes track 1For each track i, you have estimated its coolness ai. The higher ai is, the cooler track i is.
Every morning, you choose a track. The playlist then starts playing from this track in its usual cyclic fashion. At any moment, you remember the maximum coolness x of already played tracks. Once you hear that a track with coolness strictly less than x2(no rounding) starts playing, you turn off the music immediately to keep yourself in a good mood.
For each track i, find out how many tracks you will listen to before turning off the music if you start your morning with track i, or determine that you will never turn the music off. Note that if you listen to the same track several times, every time must be counted.
Input
The first line contains a single integer n (2≤n≤105), denoting the number of tracks in the playlist.
The second line contains n integers a1,a2,…,an (1≤ai≤109), denoting coolnesses of the tracks.
output
Output n integers c1,c2,…,cn, where ci is either the number of tracks you will listen to if you start listening from track i or −1 if you will be listening to music indefinitely.
Examples
Input
4
11 5 2 7
Output
1 1 3 2
Input
4
3 2 5 3
Output
5 4 3 6
Input
3
4 3 6
Output
-1 -1 -1
Note
In the first example, here is what will happen if you start with…
<dl> <dt> track 1 </dt> <dd> listen to track 1, stop as a2<a12 </dd> <dt> track 2 </dt> <dd> listen to track 2, stop as a3<a22 </dd> <dt> track 3 </dt> <dd> listen to track 3, listen to track 4, listen to track 1, stop as a2<max(a3,a4,a1)2 </dd> <dt> track 4 </dt> <dd> listen to track 4, listen to track 1, stop as a2<max(a4,a1)/2In the second example, if you start with track 4, you will listen to track 4, listen to track 1, listen to track 2, listen to track 3, listen to track 4 again, listen to track 1 again, and stop as a2<max(a4,a1,a2,a3,a4,a1)/2. Note that both track 1 and track 4 are counted twice towards the result. </dd> </dl>题目大意
给你一个可循环播放有n首歌曲的歌单，让你播放歌曲，每个歌曲都有一个优美度，（当然是按顺序播放的歌曲，播放完第n首歌曲之后播放第一首）如果播放的歌曲的优美度没有之前播放过的优美度最大值的一半，就立即停止，（这首歌就不算播放过）， 现在问你每首歌作为第一首播放的时候最多能放多少首歌，（要是能一直播放就输出-1）。
思路
我们首先想，无非两种情况：
1
要是这n首歌中最小值的二倍比最大值都大，那么怎么播放都可以一直循环，那么输出n个-1不就行了。
2
那么另一种情况就是不能一直循环，那么我们就需要一个个去判断了，如果直接暴力的话，不用想就知道肯定会爆。
但是我们想，如果当把第i首歌作为第一首歌曲播放的时候，假设播放到pos位置的时候（因为是循环播放，所以pos是一定大于i的，并且有可能大于n，所以我们要把那个数组延续到3倍左右）那样第i首歌开头的播放最大歌曲量就是（pos-i），当我们判段i+1首歌作为第一首歌的时候，只用判断pos位置的歌曲的优美度能否满足第i+1到pos-1的最大优美度的一半，那么我只用判断i+1到pos-1的区间最大值（因为在我们在判断i歌的时候就判断了i+1到pos-1是可以的，不然就不会到pos才不满足条件了，对吧）我们现在就需要能够快速找到任意区间最大值，那么就用到了rmq（区间查询）二分的思想，那么这一道题就解决了。
//GNU G++11 5.1.0
#include<bits/stdc++.h>
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<string.h>
#include<math.h>
using namespace std;
int a[1000005];
int dp[1000005][30];
int n;
void rmqinit()
{
for(int j=1;(1<<j)<=3*n;j++)
{
for(int i=1;i+(1<<j)<=3*n+1;i++)
{
dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
}
}
int rmqmax(int l,int r)
{
int k=log(r-l+1)/log(2);
return max(dp[l][k],dp[r-(1<<k)+1][k]);
}
int main()
{
scanf("%d",&n);
int ma=-1,mi=1e9;
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
a[i+n]=a[i];
a[i+2*n]=a[i];
dp[i][0]=a[i];
dp[i+n][0]=a[i];
dp[i+2*n][0]=a[i];
ma=max(ma,a[i]);
mi=min(mi,a[i]);
}
if(mi*2>=ma)
{
for(int i=0;i<n;i++)
{
printf("-1 ");
}
printf("\n");
}
else
{
rmqinit();
int pos=0;
int maxx=a[0];
for(int i=0;i<n;i++)
{
while(maxx<=2*a[pos])
{
pos++;
maxx=max(maxx,a[pos]);
}
maxx=rmqmax(i+1,pos);
printf("%d ",pos-i);
}
printf("\n");
}
return 0;
}
