題意:你有幾個搬東西的任務,從一間教室到另一間需要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; }