題目描述

著名的ACM（Advanced Computer Maker）公司租用了一層有400個房間的辦公室，結構如表1所示。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?表1 ACM公司辦公樓室示意圖

房間1	房間3	房間5	…	房間397	房間399
走廊
房間2	房間4	房間6	…	房間398	房間400

￠??這層樓沿著走廊南北向的兩邊各有200個房間。最近，公司要做一次裝修，需要在各個辦公室之間搬運辦公桌。

￠??由于走廊狹窄，辦公桌都很大，走廊里一次只能通過一張辦公桌。必須制定計劃提高搬運效率。

￠??經理制定如下計劃：一張辦公桌從一個房間移到另一個房間最多用十分鐘。當從房間i移動一張辦公桌到房間j，兩個辦公室之間的走廊都會被占用。所以，每10分鐘內，只要不是同一段走廊，都可以在房間之間移動辦公桌；如表2所示。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 表2?辦公桌移動的狀態?

?	移動辦公桌	理由
可行的	（房間30到50）和 （房間60到90）	走廊不重疊
	（房間11到12）和 （房間14到13）	走廊不重疊
不可行的	（房間20到40）和 （房間31到80）	房間31到房間40的走廊重疊
	（房間1到4）和 （房間3到6）	房間3前面的走廊重疊
	（房間2到8）和 （房間7到10）	房間7前面的走廊重疊

每個房間，只有一張辦公桌進出。現在，經理想找到一種方案，使移動桌子的事情盡快完成。請編寫程序解決經理的難題。

?

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; }

?

總結

以上是生活随笔為你收集整理的贪心算法———房间搬桌子的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。