杭电oj-1050 Moving Tables

简介: 杭电oj-1050 Moving Tables

题目:


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


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


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

image.png

输入

输入由 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)

相关文章
|
Oracle 关系型数据库 OLAP
[20170421]impdp SKIP_CONSTRAINT_ERRORS
[20170421]impdp导入问题data_options=SKIP_CONSTRAINT_ERRORS.txt --//一般年前我们经常要做一些导入导出操作,经常会遇到主键冲突问题.
1489 0
|
SQL 算法 Java
《Speedy Transactions in Multicore In-Memory Databases》
Speedy Transactions in Multicore In-Memory Databases
《Speedy Transactions in Multicore In-Memory Databases》
|
SQL 算法 关系型数据库
Optimizing Queries over Partitioned Tables in MPP Systems
随着互联网数据的爆炸性增长,传统数据库系统在单表数据容量方面承受了越来越大的压力。以前公司内部的数据库,存放的主要是来自公司业务或内部管理系统的信息,中小型公司甚至一个MySQL实例就搞定了。但现在数据源不仅更丰富,数据量也在指数级增长,从业务的角度,基于hash/range的分区表变得越来越有吸引力。
265 0
Optimizing Queries over Partitioned Tables in MPP Systems
|
安全 关系型数据库 RDS
2-minute Comparison of Online Database and Self-built Databases
Should you use Alibaba Cloud ApsaraDB for RDS or build your own database?
2252 0