poj 1083 Moving Tables

Memory: 156K

Time: 16MS

解题思路

题意：

一层楼上有400个房间，南边跟北边每边各200个，现在要在房间之间移动一些桌子，但是过道太窄了，每次只能通过一个，要求的是搬运一些桌子要花的最短时间，过道不冲突的话可以同时搬。

 

思路：

计算出每个房间前面的过道一共被走过几次，次数最多的再乘上10就是结果了。要注意的是他可能是从后往前搬，那个时候要换位。为此Wa了几次。

源程序

#include <stdio.h>
#include <string.h>
#include <conio.h>
#define N 205

void swap(int &a, int &b)
{
    int t;
    t = a;
    a = b;
    b = t;
}
int main()
{
    int i, j;
    int t, n, from, to, max, min;
    int rooms[N];

    freopen("in.txt", "r", stdin);
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        memset(rooms, 0, sizeof(rooms));

        for(i=0; i<n; i++)
        {
            scanf("%d%d", &from, &to);
            if(from > to)
                swap(from, to);
            from = (from+1) / 2;
            to = (to+1)/2;
            for(j=from; j<=to; j++)
                rooms[j]++;
        }
        min = 0;
        for(i=1; i<N; i++)
        {
            if(rooms[i] >= min)
                min = rooms[i];
        }
        printf("%d\n", min*10);
    }

    getch();
    return 0;
}