题目链接:http://poj.org/problem?id=1083
题目大意:一层里面有400个房间,北边和南边各有200个房间,要从一个房间里面把一张桌子移动到另一个房间,需要占用这两个房间之间的所有走廊(包括这两个房间前面的),每移动一个桌子需要10分钟,给出需要移动的桌子的数据(从哪移动到哪),要求计算出最少需要多少分钟才能把所有桌子移动完。

思路:在线处理:每次移动把经过的走廊占用+1,最后统计走廊的最大占用次数*10就是答案了。这里用了差分数组。时间复杂度O(n)

思考:很不错的思维题,需要注意差分的时候,y不一定大于x,要考虑是否交换x,y的值。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <math.h>
#include <bitset>
#include <algorithm>
#include <climits>

using namespace std;
#define LL long long
#define p1 first
#define p2 second
//memset(a, 0, sizeof(a));
//stack堆栈 queue队列 priority_queue优先队列
//vector向量 multiset平衡二叉树 deque双端队列
//pair{T1 first;T2 second;} greater<T>
//unordered_map 哈希map

int a[205];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(a, 0, sizeof(a));
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            int x, y;
            scanf("%d%d",&x,&y);
            x=(x+1)/2, y=(y+1)/2;
            if(x>y)
            {
                swap(x, y);
            }
            a[x]++, a[y+1]--;
        }
        for(int i=1;i<205;i++)
        {
            a[i]+=a[i-1];
        }
        cout<<*max_element(a, a+205)*10<<endl;
    }

    return 0;
}