一个疑惑
查看原帖
一个疑惑
256970
xie_lzh楼主2021/12/11 15:51

在本题的第一篇题解中,他的替换策略如下

		if(qp.top().p<qc.top().c+qpc.top().p-qpc.top().c){
			m-=qp.top().p;
			qpc.push(qp.top());
			vis[qp.top().no]=1;
			qp.pop();
		}
		else{
			m-=qc.top().c+qpc.top().p-qpc.top().c;
			vis[qc.top().no]=1;
			qpc.pop();qc.pop();
		}

而我的做法是这样的

cow pp=qp.top(),pc=qpc.top(),cc=qc.top();
		if(pp.p>cc.c+pc.p-pc.c)
		{
			m-=(cc.c+pc.p-pc.c);
			vis[cc.id]=1;
			qpc.pop();
			qpc.push(cc);
			qc.pop();
		}
		else
		{
			m-=pp.p;
			vis[pp.id]=1;
			qp.pop();
		}

显而易见这两种策略完全不同,但两者都可以AC

我对题解这种贪心策略的正确性存疑(可能是数据过水),望解答

2021/12/11 15:51
加载中...