贪心算法 ZOJ1029-MOVINGTABLES（房间搬桌子问题）

ZOJ1029-MOVINGTABLES（房间搬桌子问题）

题目背景：

¢  这层楼沿着走廊南北向的两边各有200个房间。最近，公司要做一次装修，需要在各个办公室之间搬运办公桌。

¢  由于走廊狭窄，办公桌都很大，走廊里一次只能通过一张办公桌。必须制定计划提高搬运效率。

¢  经理制定如下计划：一张办公桌从一个房间移到另一个房间最多用十分钟。当从房间i移动一张办公桌到房间j，两个办公室之间的走廊都会被占用。所以，每10分钟内，只要不是同一段走廊，都可以在房间之间移动办公

题目要求：

¢  输入

输入数据有T组测试例，在第一行给出测试例个数T。

每个测试例的第一行是一个整数N（1≤N≤200)，表示要搬运办公桌的次数。接下来N行，每行两个正整数s和t，表示一张桌子，是从房间号码s移到到房间号码t。

¢  输出

每组输入都有一行输出数据，为一整数T，表示完成任务所花费的最小时间。

思路形成：

该题属于贪心算法，因为它尽可能使搬运办公桌同时进行，以便使单独安排的搬运次数最少。这样用的时间最少，即所用最少时间为不能同时搬运桌子的次数，即某一段走廊使用次数最多（贪心标准）即为即为最少搬运时间。此题精华还在于如何把房间化为走廊。附图观看

代码实现：

#include<bits/stdc++.h>
using namespace std;
int movetable(int n)
{
    int i,j;
    int move[10000];               //桌子搬运次数
    int from,to;                   //每次搬运的起点
    memset(move, 0, sizeof(move)); //move初始化为0
    for(i=0;i<n;i++)
    {
        cin>>from>>to;
        from=(from-1)/2;
        to=(to-1)/2;               //将房间号映射为走廊号（此题精华）
        if(from>to)
            swap(from,to);         //确保from小于to

    for(j=from;j<=to;j++)          //占用走廊情况
        move[j]++;
    }
        int max=0;
        for(i=0;i<10000;i++)
            if(move[i]>max)
            max=move[i];             //走廊被占用次数最大值即为时间
       return  max*10;
}
int main()
{
   int T; //T为要测试例的个数
   int N;//每个测试例的搬桌子次数
   int i=1;
      cin>>T;
   while(cin>>N)
   {
       cout<<movetable(N)<<endl;   //如果想输出样一样，再用个数组保存即可
       if(i==T+1)             //注意T+1
        break;
        i++;
   }
    return 0;
}

最后

以上就是紧张小土豆为你收集整理的贪心算法 ZOJ1029-MOVINGTABLES（房间搬桌子问题）的全部内容，希望文章能够帮你解决贪心算法 ZOJ1029-MOVINGTABLES（房间搬桌子问题）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。