当前位置: 代码迷 >> 综合 >> POJ1083 Moving Tables(思维详解)
  详细解决方案

POJ1083 Moving Tables(思维详解)

热度:48   发布时间:2024-01-18 18:46:00.0

POJ 1083 http://poj.org/problem?id=1083

 

题目大意:

题目很长,大致意思是有400个面对面的房间,现在要从一个房间到另一个房间移动物品 ,每次花费10分钟,但是移动过程中所有的经过的走廊都会被占用,也就是不能使用,问最少移动完所有的物品需要多久。

 

解题思路:

由于每次移动过程中都会占用相关的走廊,因此我们只需要枚举每个房间前的走廊需要被占用多少次,然后取出最大值即可。

但是请注意,由于题目给出的房间图,当下界为偶数的时候,对门同样无法搬运,因此s--,同理,当上界为奇数的时候,对门同样被占用,因此需要t--。才能得出完整合理的范围(WA的心得)。

 

AC代码:

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <stack>
#include <stdlib.h>
#include <set>
//#define DEBUG
using namespace std;
typedef long long ll;
int T;
int n;
int s,t;
int d[405];
int main() {while(cin >> T) {while(T--) {cin >> n;memset(d,0, sizeof(d));while(n--) {cin >> s >> t;if(s > t) swap(s,t);if(s % 2 == 0) s--;if(t % 2 == 1) t++;for(int i = s;i <= t;i++) {d[i]++;}}sort(d,d+401,greater<int>());cout << d[0] * 10 << endl;}}return 0;
}

 

  相关解决方案