这个题目原来比赛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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
/** *//*****************************************
2
Date:2007-10-29
3
Author:littlekid
4![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
5
2844442 LittleKid 1771 Accepted 216K 0MS G++ 2063B 2007-10-29 17:12:02
6![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
7
**********************************************/
8![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
9![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
10
# include <stdio.h>
11
# include <string.h>
12![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
13
# define N 33
14![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
15
int n;
16
int tar[N];
17![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
18
int ans;
19
int stop;
20
int station[N],result[N];
21![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
22
int MIN(int a,int b)
23![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
24
return a>b?b:a;
25
}
26![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
27
void init()
28![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
29
for (int i = 1;i <= n; i ++)
30![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
31
scanf("%d",&tar[i]);
32
}
33
}
34![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
35
bool isOK(int time)
36![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
37
int t_st=1,t_ti=0;
38
int tmp;
39
stop=0;
40
for (int i=1;i<=n;i++)
41![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
50
tmp = time - t_ti + (4*t_st+20*tar[i]);
51
}
52
else
53![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
60
t_ti+= (tmp-t_st)*4;
61
}
62
else
63![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
74
void solve()
75![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
82
mid = (low+up)/2;
83
if (isOK(mid))
84![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
85![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
86
result[0]=stop;
87
for (int i=1;i<=stop;i++)
88![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
89
result[i] = station[i];
90
}
91
ans = mid;
92
}
93
up = mid;
94
}
95
else
96![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
97
low = mid+1;
98
}
99
}
100
}
101![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
102
void output()
103![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
104
printf("%d\n%d",ans,result[0]);
105
for (int i=1;i<=result[0];i++)
106![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
107
printf(" %d",result[i]);
108
}
109
printf("\n");
110
}
111![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
112
int main()
113![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
114
while (1)
115![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
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 阅读(704)
评论(0) 编辑 收藏 引用 所属分类:
Standing Programs