伊人久久大香线蕉亚洲五月天,久久天天婷婷五月俺也去,丰满少妇人妻久久久久久

pku 1771 Elevator Stopping Plan 二分+貪心判斷可行性

題意是這樣的：
一幢大樓有21層，只有一個電梯，電梯上一層樓需要4秒。停一次需要10秒，人爬一層樓需要20秒，現有一些人想通過電梯上樓，電梯選擇性的停一些樓層，使得最后一個人到達目的樓層的時間最小。
像這種最大最小問題一般思路就是二分+驗證可行性。這道題驗證可行性可采用貪心方法，即電梯停靠的越上層越好，每次停靠的樓層用不等式t-10*num-4*(i-1)-20*(j-i)=0.解出。具體看代碼吧- -
這題做的時候有點NC，竟然忘了排序。。汗。。

# include <iostream>
2

# include <vector>
3

# include <algorithm>
4

# define abs(a) ((a)>0?(a):-(a))
5

using namespace std;
6

int data[50],n;
7

void make(int limit)
8

{
9

int used=0,p=0,last=1;
10

vector<int> ans;
11

while(p<n&&10*used+(last-1)*4+abs(data[p]-last)*20<=limit)
12

p++;
13

while(p<n)
14

{
15

int up=(limit+20*data[p]+4-10*used)/24;
17

last=up;
18

ans.push_back(last);
19

p++;
20

while(p<n&&10*used+(last-1)*4+abs(data[p]-last)*20<=limit)
21

p++;
22

used++;
23

}
24

cout<<ans.size();
25

for(int i=0;i<ans.size();i++)
26

cout<<" "<<ans[i];
27

cout<<endl;
28

}
29

bool chk(int limit)
30

{
31

int used=0,p=0,last=1;
32

while(p<n&&10*used+(last-1)*4+abs(data[p]-last)*20<=limit)
33

p++;
34

while(p<n)
35

{
36

if(10*used+(data[p]-1)*4>limit) return false;
38

int up=(limit+20*data[p]+4-10*used)/24;
39

//if(up>31) up=31;
40

last=up;
41

p++;
42

while(p<n&&10*used+(last-1)*4+abs(data[p]-last)*20<=limit)
43

p++;
44

used++;
45

}
47

return true;
48

}
49

int main()
50

{
51

while(true)
52

{
53

int s=0,e=-1;
54

cin>>n;
55

if(!n) break;
56

for(int i=0;i<n;i++)
57

{
58

cin>>data[i];
59

e=((data[i]-1)*20>e?(data[i]-1)*20:e);
60

}
61

sort(data,data+n);
62

// int *p=unique(data,data+n);
63

// n=p-data;
64

while(s<=e)
65

{
66

int mid=(s+e)>>1;
67

if(chk(mid))
68

e=mid-1;
69

else
70

s=mid+1;
71

}
72

cout<<s<<endl;
73

make(s);
74

}
75

return 0;
76

}
77

posted on 2010-10-19 14:24 yzhw 閱讀(222) 評論(0) 編輯收藏引用所屬分類: search 、others

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: pku2133 Cow Imposters BFS pku 2132 Cow Math BFS pku1894-1903 Northeastern Europe 2003 解題報告 pku1213 Roman Numerals 回溯，注意數學剪枝 pku1224 PICTURE PUZZLE 拼圖游戲：回溯法 pku1223 DEHUFF 哈夫曼樹確定，PKU1261簡化版 pku 1816 wild words trie樹的活用 pku1261 Huffman Trees 搜索與數據結構結合的好題 pku 3278 Catch That Cow 簡單BFS pku 3501 Escape from Enemy Territory 二分+BFS

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

pku 1771 Elevator Stopping Plan 二分+貪心判斷可行性

導航

統計

公告

留言簿(1)

隨筆分類(227)

文章分類(2)

OJ

最新隨筆

搜索

積分與排名

最新評論

閱讀排行榜