转载请注明出处:優YoU http://user.qzone.qq.com/289065406/blog/1299062100
提示:利用房间号分割走廊,每条“子走廊”都设置一个计数器,每经过一次+1,完了最后对计数器快排,最大的次数X10就是答案
初看此题有点像贪心的感觉,因为可能会想到把输入的搬运区间的交点(临界点)进行统计,这是很笨很没效率的方法,而且要考虑一堆可能情况,我按这个思路用栈做过这题,列出了所有可能的例子,结果一致但无限WA。。。。所以呼吁大众:不要误入歧途了。。。
//Memory Time //232K 0MS #include<iostream> #include<algorithm> using namespace std; int main(void) { int room[401]; int test,move_time,i,j,temp; int from[200],to[200]; cin>>test; for(j=0;j<test;j++) { memset(room,0,sizeof(room)); //注意每次测试都要初始化,而不是在输入测试次数前初始化 cin>>move_time; for(i=0;i<move_time;i++) { cin>>from[i]>>to[i]; if(from[i]>to[i]) { temp=from[i]; from[i]=to[i]; to[i]=temp; } if(from[i]%2!=0) from[i]++; if(to[i]%2!=0) to[i]++; for(temp=from[i];temp<=to[i];temp+=2) { room[temp]++; } } sort(room,room+401); cout<<room[400]*10<<endl; } return 0; }