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

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

算法：二分+貪心

         計算出一個需要可行的時間，然后用二分法枚舉可能的解，判斷解的可行性時用貪心策略：對每個人，檢驗他能在規定時間內到達，如果不能到達，則需要多?？恳淮?，解不等式找出能?？康淖罡邩菍樱ㄗC明就算了，說明一下：因為要求的是每個人都能在指定時間能到達，所以貪心選擇使得電梯的停靠層往上同時滿足當前的人能在規定時間能到達即可，這樣再往上的人離?？康臉菍泳徒恍?#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}