题目:点击打开题目链接
巧妙的贪心。这个问题讲了一个沙王(就是DOTA里面的那货)要搬家,他有一个V大小的洞,M件装备,每件装备有两个属性,Ai是永久占用的空间,搬过来就占了,Bi是临时占用空间,除了满足洞>=Ai外,还要满足搬这件装备时,洞里的大小大于等于Bi。问能否搬完。
贪心的形式已经很熟了,但这个题的贪心排序开始排序的时候,是按Ai>Bi来排序的,结果WA。
想了想,Bi事实上是在搬完后就移除的,于是按Ai+Bi>A2i+B2i排,依然错误。
后来再仔细一想,应该是让A的永久空间尽量大(因为大东西要先搬,否则小东西多了就没有空放进去了),但Bi的临时空间要尽量小,即AI和BI的差要尽量的大,如果差一样的话应该保证BI尽量的小,因为临时空间只是门槛,实际是用不到的,所以一定要先过门槛。
#include <iostream> #include <cstring> #include <string> #include <algorithm> using namespace std; class equip { public: int ai; int bi; }; bool cmp(equip a,equip b) { if((a.ai+b.bi)!=(b.ai+a.bi)) return (a.ai+b.bi)<(a.bi+b.ai); else return a.bi<b.bi; } equip equipment[1005]; int main() { int testcase; cin>>testcase; while(testcase--) { int holev,eqnum; int pos=1; cin>>holev>>eqnum; for(int i=0;i<eqnum;i++) { cin>>equipment[i].ai>>equipment[i].bi; } sort(equipment,equipment+eqnum,cmp); for(int i=0;i<eqnum;i++) { if(holev>=equipment[i].ai && holev>=equipment[i].bi) { holev-=equipment[i].ai; } else { pos=0; break; } } if(pos==1) cout<<"Yes"<<endl; else if(pos==0) cout<<"No"<<endl; } return 0; }