ZOJ 1029

1153 ワード

テーマリンク:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=29
重なり合うところがあるなら、その重なり合うところは何度も運ぶしかないですよね.だから最初は並べ替えをして、テーブルを運んで、何回も見てみたいですが、心に底がないので、答えを見ました.
答えはまずすべてのテーブルを歩かせて、廊下の各位置を記録して、それぞれ何回か歩いたことがあります.一番多いのは10を掛けて結果です.
#include<iostream>
#include<memory.h>
using namespace std;

int Time[210];

int main()
{
    int T;

    cin>>T;
    while (T--)
    {
        memset(Time,0,sizeof(Time));
        int N, s, t;
        cin>>N;
        for (int i=0; i<N; i++)
        {
            cin>>s>>t;
            if (s % 2)
                s = (s+1)/2;
            else
                s /= 2;
            if (t % 2)
                t = (t+1)/2;
            else
                t /= 2;
            if (s > t)
            {
                int tmp = s;
                s = t;
                t = tmp;
            }
            for (int j=s; j<=t; j++)
                Time[j]++;
        }
        int MAX = 0;
        for (int j=1; j<=200; j++)
            MAX = Time[j] > MAX ? Time[j] : MAX;
        cout<<MAX*10<<endl;
    }

    return 0;
}