WA #10, 90pts ,求助
查看原帖
WA #10, 90pts ,求助
715233
Dino_chx楼主2023/9/4 17:44

看了一下大佬的方法,但是也试了,可能是我的方法不对吗,就是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;
}
2023/9/4 17:44
加载中...