这个题目原来比赛WA了，后来一直没有做出来，最近比赛又遇上，郁闷地想了好几天，我在网上没有找到正确答案，昨天向tank请教，终于知道了算法，今天AC了，写出来吧……
题目来源：ICPC2003广州赛区
题目网址：http://acm.pku.edu.cn/JudgeOnline/problem?id=1771
算法：二分+贪心
计算出一个需要可行的时间，然后用二分法枚举可能的解，判断解的可行性时用贪心策略：对每个人，检验他能在规定时间内到达，如果不能到达，则需要多停靠一次，解不等式找出能停靠的最高楼层（证明就算了，说明一下：因为要求的是每个人都能在指定时间能到达，所以贪心选择使得电梯的停靠层往上同时满足当前的人能在规定时间能到达即可，这样再往上的人离停靠的楼层就近一些……）。
我的代码风格很好（自己暂时这么认为:-)），还不清楚就看代码了……
类似题目：POJ1744http://acm.pku.edu.cn/JudgeOnline/problem?id=1744
WOJ1297 Elevator Stopping Plan
1
/** *//*****************************************
2
Date:2007-10-29
3Author:littlekid
4
52844442 LittleKid 1771 Accepted 216K 0MS G++ 2063B 2007-10-29 17:12:02
6
7
**********************************************/
8
9
10# include <stdio.h>
11# include <string.h>
12
13# define N 33
14
15int n;
16int tar[N];
17
18int ans;
19int stop;
20int station[N],result[N];
21
22int MIN(int a,int b)
23
{
24 return a>b?b:a;
25}
26
27void init()
28{
29 for (int i = 1;i <= n; i ++)
30
{
31 scanf("%d",&tar[i]);
32
}
33}
34
35bool isOK(int time)
36{
37 int t_st=1,t_ti=0;
38 int tmp;
39 stop=0;
40 for (int i=1;i<=n;i++)
41 {
42 // if (canGet(i,t_st,t_ti)) continue ;
43 if (tar[i] <= t_st) continue;
44 tmp = t_ti+(tar[i]-t_st)*20;
45 if (tmp <= time) continue ;
46
47 //getStop();
48 if (t_st == 1)
49 {
50 tmp = time - t_ti + (4*t_st+20*tar[i]);
51 }
52 else
53 {
54 tmp = time - (t_ti+10) + (4*t_st+20*tar[i]);
55 }
56 tmp /= 24;
57 if (tmp<tar[i]) return false;
58 if (t_st==1)
59 {
60 t_ti+= (tmp-t_st)*4;
61 }
62 else
63 {
64 t_ti += 10+(tmp-t_st)*4;
65 }
66 t_st = tmp;
67 stop++; station[stop]=t_st;
68 // printf("-->%d\n",t_st);
69 }
70
71 return true;
72}
73
74void solve()
75{
76 ans = tar[n]*4+20*(tar[n]-tar[1]);
77 result[0]=1; result[1]=tar[n];
78
79 int low=0,up=ans-1,mid;
80 while (low<up)
81 {
82 mid = (low+up)/2;
83 if (isOK(mid))
84 {
85 {
86 result[0]=stop;
87 for (int i=1;i<=stop;i++)
88 {
89 result[i] = station[i];
90 }
91 ans = mid;
92 }
93 up = mid;
94 }
95 else
96 {
97 low = mid+1;
98 }
99 }
100}
101
102void output()
103{
104 printf("%d\n%d",ans,result[0]);
105 for (int i=1;i<=result[0];i++)
106 {
107 printf(" %d",result[i]);
108 }
109 printf("\n");
110}
111
112int main()
113{
114 while (1)
115 {
116 scanf("%d",&n);
117 if (n == 0) break;
118 init();
119 solve();
120 output();
121 }
122 return 0;
123}
posted on 2007-10-29 21:35
R2 阅读(715)
评论(0) 编辑 收藏 引用 所属分类:
Standing Programs