P4087 最后一个点过不了a
查看原帖
P4087 最后一个点过不了a
555073
Lizzycoder楼主2022/8/19 19:33
#include<bits/stdc++.h>
using namespace std;
int n,g,rnk[100001],rlen,ans = 0;
struct node
{
	int day,num,deta;
}p[100001];
int lsh(int x)
{
	return lower_bound(rnk+1,rnk+1+rlen,x) - (rnk+1)+1;
}
bool cmp(node a,node b)
{
    return a.day < b.day;
}
struct sele
{
	int val,id;
} s[200001];
int pos[100001];//奶牛在队里的位置 重中之重 
int slen = 0;
bool findnums(int x)
{
	return (s[1].val == s[2].val || s[1].val == s[3].val);
}
void shift_up(int cur)
{
	while(cur != 1 && s[cur].val > s[cur/2].val)
	{
		swap(s[cur],s[cur/2]);
		swap(pos[s[cur].id],pos[s[cur/2].id]);
		cur /= 2;
	}
}
void shift_down(int u)
{
	while(1)
	{
		int p = u << 1;//左孩子 
		int q = p + 1;//右孩子 
		int v;//表示要和那个孩子进行比较 
		if(p > slen) //一个孩子都不在,这个u已经在最下面了 (叶子上) 
		    break;
		else if(q > slen)  v = p;
		else//两个孩子的时候,取大的孩子进行比较 
		{
			if(s[p].val > s[q].val)   v = p;
			else  v = q;
		}
		//比较s[u]和s[v] 
		if(s[u].val < s[v].val)//u号位置的元素比孩子大,不符合小根堆的性质 ,进行交换 
		{
			swap(s[u],s[v]);
			swap(pos[s[u].id],pos[s[v].id]);
			u = v; 
		}
		else break;
    }
}
int main()
{
	cin >> n >> g;
	for(int i = 1;i <= n;i++) 
	{
		scanf("%d %d %d",&p[i].day,&p[i].num,&p[i].deta);
		rnk[i] = p[i].num;
	}
	sort(rnk+1,rnk+1+n);//排序离散化 
	rlen = unique(rnk+1,rnk+1+n) - (rnk+1);//rank[1...rlen]
	sort(p+1,p+n+1,cmp);//结构体排序 
	for(int i = 1;i <= rlen;i++)
	{
		sele u;
		u.val = 0,u.id = i;
		s[++slen] = u;//第i之奶牛插在堆里slen的位置 
		pos[i] = slen;//维护上个语句   第i只奶牛在堆里的位置 
	}
	for(int i = 1;i <= n;i++)
	{
		//把第lsh(p[i].num)之奶牛 的 奶量+a[i].deta 在堆里操作 其在堆里位置为pos[lsh( a[i].num)];
		int sid = pos[lsh(p[i].num)],top = s[1].val;
		bool flag = findnums(s[1].val);
		int oldval = s[sid].val;//更新以前的val 
		s[sid].val += p[i].deta; 
		int newval = s[sid].val;//更新以后的val 
		if(p[i].deta > 0)
		{
			if(s[sid].val == top) ans++;
			if(s[sid].val > top && sid != 1) ans ++;
			if(s[sid].val > top && sid == 1 && flag == 1)  ans ++;
			shift_up(sid);//向上调整 
		}
		if(p[i].deta < 0)
		{
			shift_down(sid);//向下调整 
			if(oldval == top && newval != s[1].val) ans ++;
			if(oldval == top && newval == s[1].val && findnums(s[1].val) == 1) ans ++; 
		}
	}
	cout<<ans<<endl;
	return 0;
}
2022/8/19 19:33
加载中...