一区二区三区免费看,亚洲一区二区少妇,久久综合成人精品亚洲另类欧美

江蘇大學

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

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

1

# 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

16

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

37

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

46

}
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

78

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

只有注冊用戶登錄后才能發表評論。


相關文章: 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 管理