在本题的第一篇题解中,他的替换策略如下
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
我对题解这种贪心策略的正确性存疑(可能是数据过水),望解答