• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            USACO 0912 月賽

            Posted on 2009-12-13 21:14 rikisand 閱讀(321) 評(píng)論(0)  編輯 收藏 引用 所屬分類: Algorithm 、USACO

            silver組:

            比賽那天感冒,第一題就弄暈了,現(xiàn)在題解出來(lái)了,補(bǔ)上吧~~

            暫時(shí)只有第一題的:

            Problem 6: Bobsledding [Brian Jacokes, 2009]
            
            Bessie has entered a bobsled competition because she hopes her hefty
            weight will give her an advantage over the L meter course (2 <= L
            <= 1,000,000,000).
            
            Bessie will push off the starting line at 1 meter per second, but
            her speed can change while she rides along the course. Near the
            middle of every meter Bessie travels, she can change her speed
            either by using gravity to accelerate by one meter per second or
            by braking to stay at the same speed or decrease her speed by one
            meter per second.
            
            Naturally, Bessie must negotiate N (1 <= N <= 100,000) turns on the
            way down the hill. Turn i is located T_i meters from the course
            start (1 <= T_i <= L-1), and she must be enter the corner meter at
            a speed of at most S_i meters per second (1 <= S_i <= 1,000,000,000).
            Bessie can cross the finish line at any speed she likes.
            
            Help Bessie learn the fastest speed she can attain without exceeding
            the speed limits on the turns.
            
            Consider this course with the meter markers as integers and the
            turn speed limits in brackets (e.g., '[3]'):
            
            |   1   2   3   4   5   6   7[3]
            |---+---+---+---+---+---+---+
            |                            \
            Start                         + 8    
                                           \
                                            + 9    
                                             \
                                              + 10       +++ 14 (finish)
                                               \         /
                                          11[1] +---+---+
                                                    12  13[8]
            
            Below is a chart of Bessie's speeds at the beginning of each meter length
            of the course:
            
            Max:                              3               1       8
            Mtrs: 0   1   2   3   4   5   6   7   8   9  10  11  12  13  14 
            Spd:  1   2   3   4   5   5   4   3   4   3   2   1   2   3   4
            
            Her maximum speed was 5 near the beginning of meter 4.
            
            PROBLEM NAME: bobsled
            
            INPUT FORMAT:
            
            * Line 1: Two space-separated integers: L and N
            
            * Lines 2..N+1: Line i+1 describes turn i with two space-separated
                    integers: T_i and S_i
            
            SAMPLE INPUT (file bobsled.in):
            
            14 3
            7 3
            11 1
            13 8
            
            OUTPUT FORMAT:
            
            * Line 1: A single integer, representing the maximum speed which
                    Bessie can attain between the start and the finish line,
                    inclusive.
            
            SAMPLE OUTPUT (file bobsled.out):
            
            5

             

            題目看起來(lái)挺復(fù)雜,其實(shí)主要是求出各個(gè)turn處的最大速度,分析得到每個(gè)turn的最大速度需要滿足三個(gè)條件, M_i = min (S_i , t_i – t_{i-1} + M_{i-1} , S_k + t_k – t_i [for all k > i ] )

            因此處理每一個(gè)turn都要查詢N個(gè)turn N*N的復(fù)雜度顯然對(duì)于大數(shù)據(jù)要TLE的

            逆向思考,如果我們反過(guò)來(lái)考慮,對(duì)于每一個(gè)之后的turn來(lái)說(shuō) 如:i  如果他最大速度為 m_i

            那么 在turn i-1處,他不能超過(guò)的最大速度 m_{i-1} = min(S_i,m_i+t_i – t_{i-1});這樣成功的把后面兩個(gè)限制轉(zhuǎn)換為逆推的結(jié)果而不是向后查詢

            剩下的問(wèn)題便是如果知道兩個(gè)turn之間距離,以及turn的速度最大值,如何求出之間的最大值,畫圖顯然可以得到一種算式 maxspeed = min(s1,s2) + (dist2-dist1+abs(s1-s2))/2;

            或者 maxspeed = max(s1,s2) + (dist2 – dist1 – abs(s1-s2))/2;

            注意在開(kāi)頭和結(jié)尾加入虛擬的turn就可以了

             

            Code Snippet
            #define REP(i,n)  for(  int (i) = 0 ; i < (n) ; ++i)
            using namespace std;
            int L,N;
            struct node{
                int dist;
                int speed;
            };
            vector<node> vec;
            bool comp(const node& n1,const node& n2){
                return n1.dist<n2.dist;
            }
            vector<int> up,down;
            #define inf 98765433
            void solve()
            {
                //freopen("e:\\usaco\\bobsled.11.in","r",stdin);
                freopen("bobsled.in","r",stdin);
                freopen("bobsled.out","w",stdout);
                cin>>L>>N;
                vec.resize(N+2); up.resize(N+2,0); down.resize(N+2,0);
                vec[0].dist =0;vec[0].speed =1;
                vec[N+1].dist =L;vec[N+1].speed=inf;
                REP(i,N) scanf("%d %d",&vec[i+1].dist,&vec[i+1].speed);
                sort(vec.begin(),vec.end(),comp);
                down[N+1] = inf;
                for(int i=N;i>0;i--)
                    down[i] = min(vec[i].speed,vec[i+1].dist-vec[i].dist+down[i+1]);
                int maxspeed = 1;up[0]=1;
                for(int i=1;i<N+2;i++){
                    up[i] = min(down[i],up[i-1]+vec[i].dist - vec[i-1].dist);
                    maxspeed = max(maxspeed,min(up[i],up[i-1])+(vec[i].dist-vec[i-1].dist+abs(up[i]-up[i-1]))/2);
                }
                cout<<maxspeed<<endl;
            }


            int main()
            {
                solve();
                return 0;
            }

            ----------------------------------------------3個(gè)月后的修改線-----------------------------------------------------------------

            第一個(gè)復(fù)習(xí)周末 ,先看的這道題,過(guò)了這么久果然又杯具的不會(huì)了~~之前的解釋寫的有些模糊。

            首先,如果要想達(dá)到最快速度,那么只需要求得每個(gè)turn 能夠達(dá)到的最快速度即可~

            所以題目編程求每個(gè)turn能達(dá)到的最快速度了。首先得到簡(jiǎn)單的式子,也就是上面的min{1,2,3},第一個(gè)條件決定在這個(gè)turn我們可以加速達(dá)到的最大速度,后兩個(gè)條件為了防止滑的過(guò)快,減不下來(lái)不能通過(guò)自己以及以后的turn。按這種算法,我們必須對(duì)每一個(gè)turn遍歷之后的turn,很沒(méi)有效率。后面兩個(gè)條件是為了防止在turn處滑的過(guò)快~~那么每一個(gè)m_i 只需要滿足 min(S_i,m_{i+1}+t[i+1]-t[i]);只要這樣,就可以保證雪橇可以減速以通過(guò)下一個(gè)turn。顯然最后一個(gè)turn的 m_i 就是他的s_i,這樣遞推回去就能得到一組slowdown值,然后利用前面的式子 up[i]=min{m_i[i],up[i-1]+lenth};正向推回去就可以得到每一個(gè)turn的maxspeed。至于最大speed的算法上面已經(jīng)給出了~

            ------------------希望下次可以直接做出來(lái),不要再忘了。。。。-------------

             

             

             

             

             

             

             

             

             

             

             

             

             

             

             

            久久人人爽人人爽人人片AV麻豆 | 9999国产精品欧美久久久久久| 亚洲Av无码国产情品久久| 久久久久亚洲AV片无码下载蜜桃| 久久青青草原亚洲av无码app| 午夜精品久久久久久99热| 久久99精品久久久久婷婷| 久久国产精品免费一区| 超级碰碰碰碰97久久久久| 久久久亚洲欧洲日产国码二区| 久久国产精品-国产精品| 久久国产精品国语对白| 麻豆一区二区99久久久久| 久久99精品免费一区二区| 久久精品国产免费观看三人同眠| 国产精品欧美久久久天天影视| 精品久久久久久无码人妻热| 久久免费香蕉视频| 国产精品一区二区久久| 欧美成a人片免费看久久| 99re久久精品国产首页2020| yy6080久久| 久久久久国产视频电影| 精品久久久久久| 香蕉久久夜色精品升级完成| 亚洲精品国产综合久久一线| 热久久国产精品| 国产91色综合久久免费分享| 色婷婷综合久久久中文字幕| 欧美久久一区二区三区| 久久精品国产第一区二区| 99热热久久这里只有精品68| 国产午夜精品久久久久免费视 | 国产一区二区三区久久| 2021国内精品久久久久久影院| 国产AⅤ精品一区二区三区久久| 97久久国产综合精品女不卡| 亚洲欧美成人久久综合中文网 | 久久99九九国产免费看小说| 久久精品视屏| 伊人久久大香线蕉精品不卡 |