线段树求助
查看原帖
线段树求助
754310
Pepsee楼主2023/4/30 09:55
#include <bits/stdc++.h>
#define lson k*2
#define rson k*2+1
using namespace std;
int N,a,b;
int ans = 0,summ = 0,cnt = 0;
int h[114514] = {};
struct nd{
	int l,r,sum,maxx = 0;
	int f = 0;
}tr[114514*4+4] = {};
int Max(int now, int i) //找最大值的下标 
{
	if (tr[now].sum < tr[i].sum) return i;
	return now;
}
int cmp(int a,int b){
	return a>b;
}
void pushup(int k)
{
	tr[k].sum = tr[lson].sum + tr[rson].sum;
	tr[k].maxx = Max(tr[lson].maxx,tr[rson].maxx);
}
void pushdown(int k) //懒标记 
{    
	tr[lson].f += tr[k].f;
	tr[rson].f += tr[k].f;
	tr[lson].sum += (tr[lson].r-tr[lson].l+1) * tr[k].f;
	tr[rson].sum += (tr[rson].r-tr[rson].l+1) * tr[k].f;
	tr[k].f = 0;
}
void build(int l, int r, int k)//建树 
{
	tr[k].l = l; tr[k].r = r;
	if (l == r)
	{
		tr[k].sum = h[++cnt];
		tr[k].maxx = cnt;
	}
	int mid = (l+r) >> 1;
	build(l,mid,lson);
	build(mid+1,r,rson);
	pushup(k);
}
void add(int x,int y,int k,int c)//区间减 
{
	if(tr[k].l >= x && tr[k].r <= y)
	{
		summ -= min((tr[k].r-tr[k].l+1)*c,tr[k].sum);
		tr[k].sum -= min((tr[k].r-tr[k].l+1)*c,tr[k].sum);
		tr[k].f += c;
		return;
	}
	if(tr[k].f)
		pushdown(k);
	int mid = (tr[k].l+tr[k].r) >> 1;
	if(x <= mid) add(x,y,lson,c);
	if(y > mid) add(x,y,rson,c);
	pushup(k);
}
int main()
{
	scanf("%d %d %d",&N,&a,&b);
	for (int i = 1; i <= N; i++)
	{
		scanf("%d",&h[i]);
		summ += h[i];	
	}
	sort(h+1,h+N+1,cmp);
	build(1,N,1);
	while (true)
	{
		if (summ == 0)
		{
			printf("%d",ans);
			return 0;
		}
		int mx = tr[1].maxx;
		add(mx,mx,1,a); 
		add(1,mx-1,1,b); add(mx+1,N,1,b);
		ans++;
	}
	return 0;
}
2023/4/30 09:55
加载中...