這個題目原來比賽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 閱讀(730)
評論(0) 編輯 收藏 引用 所屬分類:
Standing Programs