贪心算法———房间搬桌子

骑猪看日落 2023-10-05 15:59 28阅读 0赞

## 题目描述 ##

**著名的****ACM****（****Advanced Computer Maker****）公司租用了一层有****400****个房间的办公室，结构如表****1****所示。**

**表1 ACM公司办公楼室示意图**

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

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

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

**表2办公桌移动的状态**

<table> 
 <tbody> 
 <tr> 
 <td>&nbsp;</td> 
 <td> 移动办公桌 </td> 
 <td> 理由 </td> 
 </tr> 
 <tr> 
 <td> 可行的 </td> 
 <td> （房间30到50）和 （房间60到90） </td> 
 <td> 走廊不重叠 </td> 
 </tr> 
 <tr> 
 <td> （房间11到12）和 （房间14到13） </td> 
 <td> 走廊不重叠 </td> 
 </tr> 
 <tr> 
 <td> 不可行的 </td> 
 <td> （房间20到40）和 （房间31到80） </td> 
 <td> 房间31到房间40的走廊重叠 </td> 
 </tr> 
 <tr> 
 <td> （房间1到4）和 （房间3到6） </td> 
 <td> 房间3前面的走廊重叠 </td> 
 </tr> 
 <tr> 
 <td> （房间2到8）和 （房间7到10） </td> 
 <td> 房间7前面的走廊重叠 </td> 
 </tr> 
 </tbody> 
</table>

**每个房间，只有一张办公桌进出。现在，经理想找到一种方案，使移动桌子的事情尽快完成。请编写程序解决经理的难题。**

**Input：**

输入数据有T组测试例，在第一行给出测试例个数（T）。每个测试例的第一行是一个整数N（1≤N≤200），表示要搬运办公桌的次数。接下来N行，每行两个正整数s和t，表示一张桌子，是从房间号码s移到房间号码t。有多组输入数据，输入第一行为一个表示输入数据总数的整数N，然后是N组输入数据。

**Ouput：**

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

**Sample Input：**

3  
4  
10 20  
30 40  
50 60  
70 80  
2  
1 3  
2 200  
3  
10 100  
20 80  
30 50

**Sample Output：**

10  
20  
30

## 思路分析 ##

该题属于贪心算法，**因为它尽可能使搬运办公桌同时进行，以便使单独安排的搬运次数最少。这样用的时间最少，即所用最少时间为不能同时搬运桌子的次数，即某一段走廊使用次数最多（贪心标准）即为即为最少搬运时间。**

**我的做法是把每一次移动办公桌的起始终点房间看成一个区间左右界限，类似于区间贪心，将第一个区间数据作为第一个移动的始末房间（看成区间），接着遍历每一个始末房间（类似于区间），如果当前的区间左界限大于上一个的区间的右界限，则表明当前的区间和上一个区间可以同时移动，共用同一时间，把该区间标记为不浪费时间，然后改变上一个区间的右界限将之设置为当前区间的右界限，接着遍历剩下的区间。**

**最后统计不能同时移动的区间（因为能同时移动的区间都已标记成了不浪费时间了）就是单独安排的搬运次数最少，也是最少搬运时间。**

## c语言源码 ##

#include<stdio.h>
 #include<stdlib.h>
 
 typedef struct qujian{
 int s;
 int e;
 int h;
 }q;
 
 int main(){
 	int i,j,temp,t,n,cnt;
 	q a[201];
 	scanf("%d",&t);
 	while(t--){
 		cnt=0;
 		scanf("%d",&n);
 		for( i=0;i<n;i++){
 			scanf("%d%d",&a[i].s,&a[i].e);
 			a[i].h=1;
 		}
 		for(i=0;i<n&&a[i].e;i++){
 		temp=a[i].e; //上一个区间的右界限
 		 for(j=0;j<n;j++){
 			 if(a[j].s>temp){ //比较当前的区间的左界限和上一个区间的右界限
 			 a[j].h=0; //标记该区间不浪费时间，即两个区间能够同时移动
 				temp=a[j].e; // 更新上一个区间的右界限 
 			 }
 		 }
 		}
 		for(i=0;i<n;i++){ //统计不能同时移动的区间
 		 if(a[i].h)
 			 cnt+=10;
 		}
 		printf("%d\n",cnt);
 	}
 return 0;
 }