pku 1771Elevator Stopping Plan

本文主要是介绍pku 1771Elevator Stopping Plan，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

有两道Elevator Stopping Plan，做了一道，另一道也顺便过了

方法是二分+贪心

一旦时间确定了，就可以用贪心来处理，只要保证每个人在时限之内到达，如果成功就进一步缩时间，不能就放宽时限。

还有一道也是这样做的。 3388 Japanese puzzle,二分枚举最大行数，一旦行数确定了，就可以用贪心的方式，看能否达到。

http://acm.pku.edu.cn/JudgeOnline/problem?id=1064,这个也是的，二分枚举+验证。

/*change from 1774*/
#include <iostream>
#define N 30001
using namespace std;
bool stop[N];
int n;
int stk[N];
bool satisfy(int t)
{
int I,J=0,nStop=0;
I=(t/20+1+1); // below(not including) walk
while (I<n)
{
while (I<n && stop[I] == false) ++I;
if (I>=n) return true;
if ((I-1)*4 + nStop*10>t)
return false;
J = (t + 4 + 20*I - 10*nStop)/24; // elevator stops here
I = (t + 16*J + 4 -10*nStop)/20 +1; // below (not inclu.) ok
++ nStop;
} 
return true;
}
void print(int t)
{
int I,J=0,nStop=0;
I=(t/20+1+1); // below(not including) walk
while (I<n)
{
while (I<n && stop[I] == false) ++I;
if (I>=n) break;
J = (t + 4 + 20*I - 10*nStop)/24; // elevator stops here
I = (t + 16*J + 4 -10*nStop)/20 +1; // below (not inclu.) ok
stk[nStop] = J;
++ nStop;
}
printf("%d",nStop);
for (int I=0; I<nStop; ++I)
{
printf(" %d",stk[I]);
}
printf("/n");
}
int main()
{
int I,J;
int high;
while (scanf("%d",&n)!=EOF)
{
if (n==0) break;
memset(stop,0,sizeof(stop));
high=0;
for (I=0; I<n; ++I)
{
scanf("%d",&J);
high=max(high,J);
stop[J] = true;
}
int maxt, mint, midt;
maxt=12*high+24;
mint=0;
n = high+1;
while (mint<=maxt)
{
midt=(mint+maxt)/2;
if (satisfy(midt))
{
maxt=midt-1;
}
else
{
mint=midt+1;
}
}
printf("%d/n",mint);
print(mint);
}
}