【贪心】BZOJ3749[POI2015]?asuchy

分析：

如果$va{l}_i?2<va{l}_{i+1}$，那么i必然选择i+1

所以，我们可以把所有这种情况全部找出来。

然后，考虑剩下的情况中，是否存在$va{l}_i<va{l}_{i+1}$的

这种情况下$i$选择$i+1$,否则$i$选择$i$即可。

由于是环，头尾会互相影响，因此两个循环各做2次

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 1000010
using namespace std;
int n;
double val[MAXN];
int ans[MAXN];
int main(){
    SF("%d",&n);	for(int i=1;i<=n;i++)SF("%lf",&val[i]);for(int i=1;i<=n;i++)if(val[i%n+1]>val[i]*2.0){
    ans[i]=i%n+1;val[i%n+1]/=2.0;}for(int i=1;ans[i]==0&&i<=n;i++)if(val[i%n+1]>val[i]*2.0){
    ans[i]=i%n+1;val[i%n+1]/=2.0;	}for(int i=n;i>=1;i--)if(val[i%n+1]>val[i]&&ans[i%n+1]!=0){
    ans[i]=i%n+1;val[i%n+1]/=2.0;	}for(int i=n;i>=1;i--)if(val[i%n+1]>val[i]&&ans[i%n+1]!=0){
    ans[i]=i%n+1;val[i%n+1]/=2.0;	}for(int i=1;i<=n;i++)if(ans[i]==0)ans[i]=i;for(int i=1;i<=n;i++)PF("%d ",ans[i]);
}