POJ1083Moving Tables

转载请注明出处：優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;
}