• <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>

            C小加

            厚德 博學(xué) 求真 至善 The bright moon and breeze
            posts - 145, comments - 195, trackbacks - 0, articles - 0
              C++博客 :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理

            foj 2077 The tallest tree (弱爆了)

            Posted on 2012-03-27 09:24 C小加 閱讀(1094) 評論(1)  編輯 收藏 引用 所屬分類: 解題報告

            看了解題報告之后我在想,為什么我會傻傻的去把每一天的高度都求出來。。。。

             

            詢問哪一天就求出哪一天的高度,把天數(shù)排一下序可以在求的過程中刪掉高度和增長速度都小的樹。時間復(fù)雜度<=O(m*n)

            #include<iostream>
            #include<cstdio>
            #include<cstring>
            #include<algorithm>
            using namespace std;
            typedef long long ll;
            const int MAXM=100003;
            typedef struct
            {
                ll high,add;//高度和增長速度
            }Tree;
            Tree tree[MAXM];
            ll day[MAXM];//實(shí)際的數(shù)天
            ll sday[MAXM];//排序后的天數(shù)
            ll ans[MAXM];//結(jié)果

            int main()
            {
                int n,m;
                while(scanf("%d %d",&n,&m)!=EOF)
                {
                    for(int i=0;i<n;++i)
                    {
                        scanf("%lld %lld",&tree[i].high,&tree[i].add);
                    }
                    for(int i=0;i<m;++i)
                    {
                        scanf("%lld",day+i);
                        sday[i]=day[i];
                    }
                    sort(sday,sday+m);//天數(shù)從小到大排序
                    memset(ans,0,sizeof(ans));
                    Tree tmax;
                    for(int i=0;i<m;++i)//枚舉排序后的天數(shù)
                    {
                        tmax.high=tree[0].high+sday[i]*tree[0].add;
                        tmax.add=tree[0].add;
                        int pos=1;
                        for(int j=1;j<n;++j)//枚舉每一顆樹
                        {
                            Tree temp=tree[j];
                            temp.high+=sday[i]*tree[j].add;
                            if( !(tmax.high>=temp.high&&tmax.add>=temp.add) )//如果第j棵樹在sday[i]的高度和增長速度都小于某棵樹,則舍棄第j棵樹
                            {
                                tree[pos++]=tree[j];
                            }
                            //找到在sday[i]時刻高度最大的樹
                            if(tmax.high<temp.high)
                            {
                                tmax=temp;
                            }
                        }
                        n=pos;
                        ans[ sday[i] ]=tmax.high;
                    }

                    for(int i=0;i<m;++i)
                        printf("%lld\n",ans[ day[i] ]);

                }

                return 0;
            }

             

            Feedback

            # re: foj 2077 The tallest tree (弱爆了)  回復(fù)  更多評論   

            2012-03-27 09:39 by tb
            呵呵
            久久精品国产亚洲Aⅴ香蕉| 亚洲国产另类久久久精品 | 久久香蕉综合色一综合色88| 香蕉久久夜色精品升级完成| 亚洲精品成人网久久久久久| 久久精品这里只有精99品| 久久久久国产| 精品久久综合1区2区3区激情| 国产精品免费久久久久久久久 | 久久妇女高潮几次MBA| 2021国产精品久久精品| 伊人久久无码中文字幕| 国产美女亚洲精品久久久综合| 亚洲精品无码专区久久久| 7777精品久久久大香线蕉| 精品久久久久久国产| 久久狠狠色狠狠色综合| 观看 国产综合久久久久鬼色 欧美 亚洲 一区二区 | 欧美伊香蕉久久综合类网站| 久久精品国产99国产精品| 久久久久婷婷| 精品久久亚洲中文无码| 99久久综合狠狠综合久久止| 久久精品18| 青青热久久综合网伊人| 国内精品伊人久久久久av一坑| 亚洲va久久久久| 一极黄色视频久久网站| 日本高清无卡码一区二区久久| 亚洲一区中文字幕久久| 久久亚洲私人国产精品vA| 久久人与动人物a级毛片| 中文字幕精品无码久久久久久3D日动漫 | 品成人欧美大片久久国产欧美...| 久久亚洲精精品中文字幕| 亚洲愉拍99热成人精品热久久| 亚洲国产综合久久天堂| 欧美伊人久久大香线蕉综合| 久久久久久久久久久| 7777精品久久久大香线蕉| 久久人妻少妇嫩草AV无码专区|