久久不见久久见免费视频7,老男人久久青草av高清,久久久久久狠狠丁香

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

題意是這樣的：
一幢大樓有21層，只有一個(gè)電梯，電梯上一層樓需要4秒。停一次需要10秒，人爬一層樓需要20秒，現(xiàn)有一些人想通過(guò)電梯上樓，電梯選擇性的停一些樓層，使得最后一個(gè)人到達(dá)目的樓層的時(shí)間最小。
像這種最大最小問(wèn)題一般思路就是二分+驗(yàn)證可行性。這道題驗(yàn)證可行性可采用貪心方法，即電梯停靠的越上層越好，每次停靠的樓層用不等式t-10*num-4*(i-1)-20*(j-i)=0.解出。具體看代碼吧- -
這題做的時(shí)候有點(diǎn)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) 評(píng)論(0) 編輯收藏引用所屬分類: search 、others

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！

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

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理

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

導(dǎo)航

統(tǒng)計(jì)

公告

留言簿(1)

隨筆分類(227)

文章分類(2)

OJ

最新隨筆

搜索

積分與排名

最新評(píng)論

閱讀排行榜