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))
 5using namespace std;
 6int data[50],n;
 7void 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}
29bool 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}
49int 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 阅读(259) 评论(0)  编辑 收藏 引用 所属分类: search 、others


只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理


<2011年2月>
日一二三四五六
303112345
6789101112
13141516171819
20212223242526
272812345
6789101112

导航

统计

公告

统计系统

留言簿(1)

随笔分类(227)

文章分类(2)

OJ

最新随笔

搜索

积分与排名

最新评论

阅读排行榜