The famous ACM (Advanced Computer Maker) Company has rented a floor of a building whose shape is in the following figure.
The floor has 200 rooms each on the north side and south side along the corridor. Recently the Company made a plan to reform its system. The reform includes moving a lot of tables between rooms. Because the corridor is narrow and all the tables are big, only one table can pass through the corridor. Some plan is needed to make the moving efficient. The manager figured out the following plan: Moving a table from a room to another room can be done within 10 minutes. When moving a table from room i to room j, the part of the corridor between the front of room i and the front of room j is used. So, during each 10 minutes, several moving between two rooms not sharing the same part of the corridor will be done simultaneously. To make it clear the manager illustrated the possible cases and impossible cases of simultaneous moving.
For each room, at most one table will be either moved in or moved out. Now, the manager seeks out a method to minimize the time to move all the tables. Your job is to write a program to solve the manager’s problem.
Input
The input consists of T test cases. The number of test cases ) (T is given in the first line of the input. Each test case begins with a line containing an integer N , 1<=N<=200 , that represents the number of tables to move. Each of the following N lines contains two positive integers s and t, representing that a table is to move from room number s to room number t (each room number appears at most once in the N lines). From the N+3-rd line, the remaining test cases are listed in the same manner as above.
Output
The output should contain the minimum time in minutes to complete the moving, one per line.
Sample Input
3 4 10 20 30 40 50 60 70 80 2 1 3 2 200 3 10 100 20 80 30 50
Sample Output
10 20 30
需要注意的是房间与走廊的位置关系，就如图中所给的图片所示
相对门的两个房间占用同一处走廊，所以例如有1——3和4——6移动方式时，它们是共享了同一段走廊的，即3号房间门前的走廊。
分析过程有如下图所示
C++版本一
#include <cstdio>
#include <algorithm>
using namespace std;
#define SIZE 205
struct Data_Type
{
int from, to;
bool flag;
}moving[SIZE];
bool Cmp(const Data_Type a, const Data_Type b)
{
return a.from < b.from;
}
int main(void)
{
int i, testNum, n;
scanf("%d", &testNum);
while (testNum-- != 0)
{
scanf("%d", &n);
for (i = 0; i < n; i++)
{
scanf("%d%d", &moving[i].from, &moving[i].to);
if (moving[i].from > moving[i].to)
{
int temp = moving[i].from;
moving[i].from = moving[i].to;
moving[i].to = temp;
}
if (moving[i].from % 2 == 0)
{
moving[i].from--;
}
if (moving[i].to % 2 == 1)
{
moving[i].to++;
}
moving[i].flag = false;
}
sort(moving, moving+n, Cmp);
bool completion = false;
int count = -1, priorTo;
while (!completion)
{
completion = true;
count++;
priorTo = 0;
for (i = 0; i < n; i++)
{
if (!moving[i].flag && moving[i].from > priorTo)
{
moving[i].flag = true;
priorTo = moving[i].to;
completion = false;
}
}
}
printf("%d\n", count*10);
}
return 0;
}
C++版本二
#include <stdio.h>
#include <string.h>
#define SIZE 405
int main(void)
{
int count[SIZE];
int i, j, testNum, n, max, from, to;
scanf("%d", &testNum);
while (testNum-- != 0)
{
scanf("%d", &n);
memset(count, 0, sizeof(count));
for (i = 0; i < n; i++)
{
scanf("%d %d", &from, &to);
if (from > to)
{
int temp = from;
from = to;
to = temp;
}
if (from % 2 == 0)
{
count[from-1]++;
}
if (to % 2 == 1)
{
count[to+1]++;
}
for (j = from; j <= to; j++)
{
count[j]++;
}
}
max = 0;
for (i = 0; i < SIZE; i++)
{
if (count[i] > max)
{
max = count[i];
}
}
printf("%d\n", max*10);
}
return 0;
}
C++版本三
思路：
最开始的思路就是模拟，首先把两边归为一边，按起点将所有交换排序后，每次都贪心的拿一遍，这样最后可以得到拿的次数。因为数据量不大，即便是O(n^2)的时间复杂度也不会超时，所以很快写出来了。但是却WA的很惨。。。虽然对贪心的思路不太确定，但是没找到反例。
后来参考了网上的做法，基本上都是遍历每一个交换区间，用一个数组记录过道i被遍历的次数，这样遍历次数最多的那个区间的次数乘以10，就是最少需要的时间。这个思路的证明可以参考这个回答：http://poj.org/showmessage?message_id=347563
这个思路确实十分巧妙，但是我还是一直在纠结我的算法为什么会错。尝试着证明了一下，发现对于经过次数最多的那个过道，我的每一次遍历也是一定经过它的，并且遍历的次数也不可能小于经过这个过道的次数（每次最多拿一个），所以也就是说遍历的次数一定等于经过次数最多的过道的次数，也就是说两个算法是等价的。后面经过调试发现思路确实是对的，WA在了中间对于每次遍历点的标记。
这道题收获还是很多的，坚持了自己的算法没有盲从，并且最后通过调试得到了证明。两个算法在时间复杂度上想通，我的空间复杂度可能更到一些，但是思路更加直接，如果是比赛的时候的话还是直接点好吧。
PS：中间cb罢工无法调试，搞了半天解决不了，结果搁置了两天自己好了。。。终于把这道题给debug了出来。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
struct Node{
int sta;
int en;
};
const int MAX = 210;
bool cmp(const Node& n1, const Node& n2){
if( n1.sta != n2.sta ){
return n1.sta<n2.sta;
}
return n1.en<n2.en;
}
int T;
int N;
int res;
Node lis[MAX];
bool flag[MAX];
int path[MAX];
int main(){
scanf("%d",&T);
while( T-- ){
scanf("%d",&N);
int a,b;
res = 0;
memset(flag,false,sizeof(flag));
for( int i = 0; i < N; i++ ){
scanf("%d%d",&a,&b);
if( a%2 == 0 ){
a /= 2;
}
else{
a = (a-1)/2+1;
}
if( b%2 == 0 ){
b /= 2;
}
else{
b = (b-1)/2+1;
}
if( a > b ){
swap(a,b);
}
lis[i].sta = a;
lis[i].en = b;
}
int pos = 0;
int dis = 0;
sort(lis,lis+N,cmp);
for( int i = 0; i < N; i++ ){
if( flag[i] == true ){
continue;
}
pos = i+1;
flag[i] = true;
dis = lis[i].en;
res++;
while( pos < N ){
if( flag[pos] == true ){
pos++;
continue;
}
if( lis[pos].sta > dis ){
flag[pos] = true;
dis = lis[pos].en;
}
pos++;
}
}
printf("%d\n",res*10);
}
return 0;
}
C++版本四
简单的方法便是区间覆盖的方法：
首先便是走廊附属问题1号房间和2号房间都对应位置1号的走廊，3号房间和四号房间对应2号走廊，如此，便是有200个这样的位置，然后我们通过观察就可以发现两边的规律，走廊号 = （房间号 + 1）/ 2(用位运算便是 >> 1).
接着就是区间覆盖方面的问题了，大家首先看完题目后，就能在心里确定一个最核心的东西，便是时间的多少，取决于相互覆盖接触的区间的多少，应该他们无法同时进行移动，如此便可以运用区间覆盖的思想，对于整体的200个走廊区间，用一个数组X[MAXN]去标记我这个走廊在我所有的移动区间中被覆盖了多少次，由于这些覆盖了同一个走廊的移动是不能够同时发生的，所以我们选取其中最大的一个数便是不能同时发生的区间移动的次数，答案便是如此。
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <vector>
#include <cctype>
#include <cstdio>
#include <string>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define pb push_back
#define mp make_pair
#define fillchar(a, x) memset(a, x, sizeof(a))
#define copy(a, b) memcpy(a, b, sizeof(a))
#define lson rt << 1, l, mid
#define rson rt << 1|1, mid + 1, r
typedef long long LL;
typedef pair<int, int > PII;
typedef unsigned long long uLL;
template<typename T>
void print(T* p, T* q, string Gap = " ") {
int d = p < q ? 1 : -1;
while(p != q) {
cout << *p;
p += d;
if(p != q) cout << Gap;
}
cout << endl;
}
template<typename T>
void print(const T &a, string bes = "") {
int len = bes.length();
if(len >= 2)cout << bes[0] << a << bes[1] << endl;
else cout << a << endl;
}
const int INF = 0x3f3f3f3f;
const int MAXM = 2e5;
const int MAXN = 200 + 5;
int T, N;
int X[MAXN];
int main(){
scanf("%d", &T);
while(T --){
scanf("%d", &N);
int a, b, res = 0;
memset(X, 0, sizeof(X));
for(int i = 0;i < N;i ++){
scanf("%d%d", &a, &b);
if(a > b) swap(a, b);
a = (a + 1) >> 1;
b = (b + 1) >> 1;
for(int i = a;i <= b;i ++){
X[i] ++;
res = max(res, X[i]);
}
}
printf("%d\n", res * 10);
}
return 0;
}
京公网安备 11010502036488号