问一个愚蠢的问题,求大佬们解答
查看原帖
问一个愚蠢的问题,求大佬们解答
1028990
w2y51c318楼主2023/8/23 19:36
int n,cnt,f[MAX];
    pii a[MAX],d[MAX];
    signed q[MAX],head,tail;
    #define X(i) (d[i+1].fi)
    #define Y(i) ((-f[i]))

    inline void mian()
    {
    	read(n);
    	for(int i=1;i<=n;++i) read(a[i].fi,a[i].se);
    	sort(a+1,a+n+1,[&](pii x,pii y){return x.fi==y.fi?x.se>y.se:x.fi>y.fi;});
    	for(int i=1;i<=n;++i) if(d[cnt].se<a[i].se) d[++cnt]=a[i];
    	q[1]=0,head=1,tail=1;
    	for(int i=1;i<=cnt;++i)
    	{
    		while(head<tail&&1.0*(Y(q[head+1])-Y(q[head]))/(X(q[head+1])-X(q[head]))<=d[i].se) ++head;
    		f[i]=f[q[head]]+d[q[head]+1].fi*d[i].se;
    		while(head<tail&&(Y(q[tail])-Y(q[tail-1]))*(X(i)-X(q[tail]))>=(Y(i)-Y(q[tail]))*(X(q[tail])-X(q[tail-1]))) --tail;
    		q[++tail]=i;
		}
    	write(f[cnt],'\n');
    }

下面这段代码可以通过本题,但是将第 16 行的

while(head<tail&&1.0*(Y(q[head+1])-Y(q[head]))/(X(q[head+1])-X(q[head]))<=d[i].se) ++head;

替换成

while(head<tail&&Y(q[head+1])-Y(q[head])<=d[i].se*(X(q[head+1])-X(q[head]))) ++head;

就会出现队首无法弹出的问题,这是为什么呢?

2023/8/23 19:36
加载中...