当前位置: 代码迷 >> 综合 >> 杭电oj-1050 Moving Tables
  详细解决方案

杭电oj-1050 Moving Tables

热度:107   发布时间:2023-11-22 07:00:03.0

题目:
著名的ACM(高级计算机制造商)公司租用了一栋建筑的地板,其形状如下。

楼北侧和走廊南侧各有200间客房。最近,公司制定了一项改革体制的计划。改革包括在房间之间移动许多桌子。因为走廊很窄,所有的桌子都很大,只有一张桌子能穿过走廊。需要一些计划来使移动高效。经理想出了以下计划:在 10 分钟内将桌子从房间移到另一个房间即可完成。当将一张桌子从 i 房间移到房间 j 时,使用 I 房间前面和房间 j 前面之间的走廊部分。因此,在每 10 分钟内,两个房间之间将同时进行几次移动,这些房间不共享走廊的同一部分。为了清楚说明经理说明了可能同时移动的案例和不可能的情况。

对于房间,最多只能搬一张桌子或搬出。现在,经理正在寻找一种方法,以最大限度地减少移动所有表格的时间。你的工作是写一个程序来解决经理的问题。

输入
输入由 T 测试案例组成。测试案例的数量)(T 在输入的第一行中给出。每个测试案例以包含整数 N、1+lt 和+200 的行开头,该行表示要移动的表数。以下 N 行中的每条都包含两个正整数 s 和 t,表示一张桌子将从房间号 t 移动到房间号 t(每个房间编号最多出现在 N 行中一次)。从 N+3-rd 行中,其余测试案例以与上述相同的方式列出。

输出
输出应包含完成移动的最短时间,每行一个。

示例输入
3
4
10 20
30 40
50 60
70 80
2
1 3
2 200
3
10 100
20 80
30 50

样本输出
10
20
30

代码(可AC):

//定义数组存储走廊(桌子编号==走廊编号)
/* 贪心算法,找到重复数量最多的走廊 */
#include<stdio.h>
int main()
{
    int room[200];int i,j,k,s,t,T,N,temp,max; scanf("%d",&T);//T:测试组数for(i=0;i<T;i++){
    for(j=0;j<200;j++){
    room[j]=0; //将数组初始化}scanf("%d",&N); //每一组共有N行for(j=0;j<N;j++){
    scanf("%d %d",&s,&t);//读入每一行的两个房间号s=(s-1)/2;//细节 将房间号处理为数组编号t=(t-1)/2;if(s>t)//读入的房间号可能先大后小 eg:20 10 细节{
    temp=s;s=t;t=temp;}//将房间号都是从小到大for(k=s;k<=t;k++)//需要移动的桌子所经过的数组元素+1;{
    room[k]++;}}max=0;for(j=0;j<200;j++)//将所有的数组元素(走廊)筛选出最大值{
    if(max<room[j]){
    max=room[j];	}	} printf("%d\n",max*10);//每一次搬桌子需要10min}return 0;} 

注意:
1:多重循环时要合理的区分和使用i,j ,k
2:注意细节
3:将实际问题抽象化
4:\n的使用(过AC)

  相关解决方案