這個題目原來比賽WA了，后來一直沒有做出來，最近比賽又遇上，郁悶地想了好幾天，我在網上沒有找到正確答案，昨天向tank請教，終于知道了算法，今天AC了，寫出來吧……

題目來源：ICPC2003廣州賽區
題目網址：http://acm.pku.edu.cn/JudgeOnline/problem?id=1771

算法：二分+貪心

         計算出一個需要可行的時間，然后用二分法枚舉可能的解，判斷解的可行性時用貪心策略：對每個人，檢驗他能在規定時間內到達，如果不能到達，則需要多停靠一次，解不等式找出能停靠的最高樓層（證明就算了，說明一下：因為要求的是每個人都能在指定時間能到達，所以貪心選擇使得電梯的?？繉油贤瑫r滿足當前的人能在規定時間能到達即可，這樣再往上的人離?？康臉菍泳徒恍?#8230;…）。
        我的代碼風格很好（自己暫時這么認為:-)），還不清楚就看代碼了……

類似題目：POJ1744http://acm.pku.edu.cn/JudgeOnline/problem?id=1744
                    WOJ1297  Elevator Stopping Plan

  1/** *//*****************************************
  2Date: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}