2326 Moving Tables 贪心

题目大意:有400个箱子,奇数的箱子在北边,,偶数的箱子在南边,每个箱子的大小都一样。北边和南边之间有一条走廊,走廊的宽度刚好是一个箱子的宽度。 现在有M个移动操作,工人每次移动箱子需要10分钟(你有无限个工人,因为有走廊的约束,不能有两个箱子公用一段走廊)。问需要多少分钟能把这些操作做完

解题思路:先将奇数的箱子和偶数的箱子做一下处理,避免1 3和4 6操作只需要10分钟这种情况。输入的时候要注意,输入的第一个数有可能小于第二个数。

;const int N = 210;struct Room{int x, y;}R[N];int n, vis[N];int cmp(const Room &a, const Room &b) {if(a.x == b.x) {return a.y > b.y;}elsereturn a.x < b.x;}void init() {scanf(“%d”, &n);int x, y;for(int i = 0; i < n; i++) {scanf(“%d%d”, &x, &y);if(x > y) {int t = x;x = y;y = t;}R[i].x = x % 2 ? x : x – 1;R[i].y = y % 2 ? y : y – 1;}sort(R, R + n, cmp);memset(vis, 0, sizeof(vis));}int solve() {int cnt = 0;int mark = 0;while(1) {int l = -10;for(int i = 0; i < n; i++) {if(!vis[i] && R[i].x > l) {vis[i] = 1;l = R[i].y;mark++;}}cnt++;if(mark == n)break;}return cnt * 10;}int main() {int test;scanf(“%d”, &test);while(test–) {init();printf(“%d\n”, solve());}return 0;}

使用双手的是劳工,使用双手和头脑的舵手,

2326 Moving Tables 贪心

相关文章:

你感兴趣的文章:

标签云: