题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=1050
题意
有一条走廊，走廊两边各有200个房间，一边的房间编号是奇数，另一边是偶数。现在有n个箱子需要从一个房间移动到另一个房间，移动一个箱子需要10分钟，箱子可以同时移动，但某一段走廊每次只能移动1个箱子，比如（1,3）和（6,8）可以同时移动，而（1,5）和（6,8）不能同时移动，求最少需要多少时间可以把箱子移动完毕。
思路
先将箱子按开始的房间号由小到大排序，然后循环遍历，在遍历的过程中不断去除可以同时移动的箱子（表示箱子已移动完毕），记录循环的次数，直到所有的箱子均已移动完毕。循环次数*10即是答案。由于这是区间相交问题，所以要将所有的房间号映射到一维坐标系中，根据题目中的图可知，对于房间号为k的房间来说（k为偶数），房间k和房间k-1是相对的，也就是偶数k和k-1在坐标轴上对应的是同一位置，所以要将所有编号为偶数k的房间的编号转化成k-1.
代码
1 #include <algorithm> 2 #include <iostream> 3 #include <cstring> 4 #include <cstdio> 5 #include <vector> 6 using namespace std; 7 8 struct Node 9 { 10 int s, e; 11 bool visit; //记录箱子是否已经移动完毕，值为true则移动完毕 12 13 Node(int s, int e) :s(s), e(e), visit(false) {} 14 bool operator < (const Node& node)const 15 { 16 return s < node.s; //将房间按开始房间号从小到大排序 17 } 18 }; 19 20 int main() 21 { 22 //freopen("hdoj1050.txt", "r", stdin); 23 vector<Node> v; 24 int m, n; 25 cin >> m; 26 while (m--) 27 { 28 cin >> n; 29 v.clear(); 30 int s, e; 31 for (int i = 0; i<n; i++) 32 { 33 cin >> s >> e; 34 if (s > e) //注意输入的开始房间号可能大于结束房间号 35 swap(s, e); 36 if (s % 2 == 0) //房间号为偶数的，要变成该偶数的前一个奇数 37 s--; 38 if (e % 2 == 0) 39 e--; 40 v.push_back(Node(s, e)); 41 } 42 43 sort(v.begin(), v.end()); 44 int ans = 0; //记录循环的次数 45 int cnt = 0; //记录已经移动完毕的箱子的个数 46 int cur = 0; //当前从第cur个箱子开始遍历 47 int t; 48 while (cnt != n) 49 { 50 for (int i = 0; i<n; i++) 51 { 52 if (!v[i].visit) 53 { 54 cur = i; 55 t = v[i].e; 56 v[i].visit = true; 57 cnt++; 58 break; 59 } 60 } 61 for (int i = cur+1; i<n; i++) 62 { 63 if (!v[i].visit && v[i].s > t) 64 { 65 cnt++; 66 t = v[i].e; 67 v[i].visit = true; 68 } 69 } 70 ans++; 71 } 72 cout << ans * 10 << endl; 73 } 74 return 0; 75 }
注意点
1、要按开始房间号从小到大排序，而不是结束房间号。手动运行下面的数据有助于理解：
1 4 2 10 4 6 8 16 12 14
2、输入的开始房间号可能大于结束房间号，此时要将两者交换；
3、对于编号为偶数k的房间，需将其编号转为奇数k-1
测试数据
输入：
3 2 1 3 4 6 4 1 20 2 10 11 19 15 16 4 2 10 4 6 8 16 12 14
输出：
20 30 20