UVALive 2326 Moving Tables 贪心

题意：你有几个搬东西的任务，从一间教室到另一间需要10分钟，但是在此期间，你需要经过的走廊不能又其他任务占用，求最短时间。

教室分布如下：

很明显的贪心，其实就是找出最少有几个不相交区间就可以了，循环找出来，复杂度为O(n^2)，这样是可行的，因为数据量不是很大，只到200。

但是如果数据量大点就会超时了，于是我想了个o(nlogn+n)的办法，排序后遍历一遍，拿个数组记录每一组不相交区间的最末尾的值，每次查询能不能放到某组区间里面，能就放进去，不能就再开辟一个数组。

比较坑的是输入的两个房间不一定是左边大于右边，在这里wa了一次。

代码：

 /* 
 *   Author:        illuz <iilluzen[at]gmail.com> 
 *   Blog:          http://blog.csdn.net/hcbbt 
 *   File:          uvalive2326.cpp 
 *   Lauguage:      C/C++ 
 *   Create Date:   2013-09-07 14:19:24 
 *   Descripton:    UVALive 2326 Moving Tables, greedy  
 */  
#include <cstdio>  
#include <cstring>  
#include <algorithm>  
using namespace std;  
#define rep(i, n) for (int i = 0; i < (n); i++)  
#define mc(a) memset(a, 0, sizeof(a))  
  
const int MAXN = 210;  
struct P {  
    int lhs, rhs;  
} p[MAXN];  
int t, n, vis[MAXN], rec[MAXN], a, b;  
  
bool cmp(P a, P b) {  
    return a.lhs < b.lhs;  
}  
  
int main() {  
    scanf("%d", &t);  
    while (t--) {  
        scanf("%d", &n);  
        if (n == 0) {  
            printf("0\n");  
            continue;  
        }  
        rep(i, n) {  
            scanf("%d%d", &a, &b);  
            a = (a + 1) / 2;  
            b = (b + 1) / 2;  
            if (a == b) i--, n--;  
            else {  
                p[i].lhs = min(a, b);  
                p[i].rhs = max(a, b);  
            }  
        }  
        sort(p, p + n, cmp);  
        int ans = 0;  
        mc(vis); mc(rec);  
        for (int i = 0; i < n; i++) {  
            if (vis[i] == 0) {  
                vis[i]++;  
                int ok = false;  
                for (int j = 1; j <= ans && !ok; j++)  
                    if (rec[j] < p[i].lhs)  
                        rec[j] = p[i].rhs, ok = true;  
                if (!ok)  
                    rec[++ans] = p[i].rhs;  
            }  
        }  
        if (ans == 0) printf("10\n");  
        else printf("%d\n", ans * 10);  
    }  
    return 0;   
}

补充：软件开发 , C++ ,