本文主要是介绍POJ 1083 Moving Tables 贪心，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：已知有400个房间，有n张桌子必须从a 房间搬到 b 房间，搬每张桌子所花的时间都是10分钟。走廊上每次只能容下一张桌子，但是不同的地方允许同时搬运。求将所有的桌子全部搬完最少要花多少时间。
题解：给出两种解法。
#include <cstdlib>
#include <iostream>
using namespace std;
struct item
{
int a, b, flag;
} move [201];
int cmp ( const void *x, const void *y )
{
struct item *c,*d;
c=(struct item *)x;
d=(struct item *)y;
return c->a - d->a;
}
int main()
{
int T;
cin >> T;
while ( T-- )
{
int n, i, j;
cin >> n;
for ( i = 0; i < n; i++ )
{
cin >> move[i].a >> move[i].b;
if ( move[i].a > move[i].b )
swap ( move[i].a, move[i].b );
if ( move[i].a % 2 == 0 )
move[i].a --;
if ( move[i].b % 2 == 1 )
move[i].b ++;
move[i].flag = 0;
}
qsort ( move, n , sizeof(struct item), cmp );
int index, counter = n * 10;
for ( i = 0; i < n-1; i++ )
{
index = i;
if ( move[i].flag != 1 )
{
for ( j = i+1; j < n; j++ )
{
if ( move[j].flag != 1 && move[i].b < move[j].a )
{
move[j].flag = 1;
counter -= 10;
i = j;
}
}
i = index;
}
}
cout << counter << endl;
}
return 0;
}
当然下面的做法也可以。因为若在某一段（任意长）的走廊上，花的时间最长，那么这段这段时间就代表了总时间。因此，我们只需要找出最繁忙的走廊所经历的次数（最大次数），再乘以10，即得总时间。
#include <iostream>
using namespace std;
int main()
{
int t;
cin >> t;
while ( t-- )
{
int n, start, end, i, j;
int corridor[201] = { 0 };
cin >> n;
for ( i = 0; i < n; i++ )
{
cin >> start >> end;
if ( start > end )
swap ( start, end );
for ( j = ( start - 1 ) / 2; j <= ( end - 1 ) / 2; j++ )
++corridor[j];
}
int max = -1;
for ( i = 0; i < 201; i++ )
if ( corridor[i] > max )
max = corridor[i];
cout << max * 10 << endl;
}
return 0;
}
这篇关于POJ 1083 Moving Tables 贪心的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
