大寄,优先队列求助
查看原帖
大寄,优先队列求助
726870
Rainber楼主2023/12/18 19:54
#include<stdio.h>
#include<stdbool.h>
#define MAXN 100000
#define INF 2147483647
long long fum[MAXN+1];
int q[MAXN][2],hq,tq,min=INF;
int q2[MAXN][2],hq2,tq2; 
int main()
{
	int n,m,i,f,s;
	scanf("%d%d",&n,&m);
	for(i=0;i<n;++i)
	{
		scanf("%d%d",&f,&s);
		fum[i+1]=fum[i]+f;
		while(tq<hq&&s>=q[hq-1][0])
		{
			hq--;
		}
		q[hq][0]=s;
		q[hq][1]=i;
		hq++;
		q2[hq2][0]=s;
		q2[hq2][1]=i;
		hq2++;
		while(tq2<hq2&&fum[q2[hq2-1][1]+1]-fum[q2[tq2][1]]>=m)
		{
			if(q2[tq2][1]==q[tq][1])
			{
				tq++;
			}
			tq2++;
		}
		min=(min<q[tq][0]?min:q[tq][0]);
	}
	printf("%d",min);
	return 0;
}

求助,寄录。 第二个点差了10倍多,不知为何。。。

2023/12/18 19:54
加载中...