看了一下大佬的方法,但是也试了,可能是我的方法不对吗,就是WA
#include<bits/stdc++.h>
#define inf 2022093020220930
#define ll long long
using namespace std;
const int N=1e5+7;
int n,a[N];
vector<int> ans;
struct Segment_Tree
{
struct maintain
{
int l,r;
ll sum,minn;
}tree[N<<2];
void pushup(int x)
{
tree[x].sum=tree[x<<1].sum+tree[x<<1|1].sum;
tree[x].minn=min(tree[x<<1].minn,tree[x<<1|1].minn);
return;
}
void build(int x,int l,int r)
{
tree[x]={l,r,0,inf};
if(l==r)
{
tree[x].sum=tree[x].minn=a[l];
return;
}
int mid=l+r>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
pushup(x);
return;
}
ll query_sum(int x,int l,int r)
{
if(l<=tree[x].l&&r>=tree[x].r)
return tree[x].sum;
ll res=0;
int mid=tree[x].l+tree[x].r>>1;
if(l<=mid)
res+=query_sum(x<<1,l,r);
if(r>mid)
res+=query_sum(x<<1|1,l,r);
return res;
}
ll query_min(int x,int l,int r)
{
if(l<=tree[x].l&&r>=tree[x].r)
return tree[x].minn;
ll res=inf;
int mid=tree[x].l+tree[x].r>>1;
if(l<=mid)
res=min(res,query_min(x<<1,l,r));
if(r>mid)
res=min(res,query_min(x<<1|1,l,r));
return res;
}
}tree;
int main()
{
// freopen("P4086_10.in","r",stdin);
// freopen("xiabb.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
tree.build(1,1,n);
double MINN=-1;
for(int i=1;i<=n-2;i++)
{
ll len=n-i,cur=tree.query_sum(1,i+1,n)-tree.query_min(1,i+1,n);
if((double)cur/len>MINN)
{
MINN=(double)cur/len;
ans.clear();
ans.push_back(i);
}
else if((double)cur/len==MINN)
ans.push_back(i);
}
for(auto it:ans)
{
printf("%d ",it);
}
return 0;
}