亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

ZOJ 3194 Coverage(貪心)

系統 2126 0

題意:對于題目給的點,x固定,而與x組合的y可以任意交換,求如何安置y可使這些點組成線段下面的面積最大,最大面積是多少

分析:可以發現Xn-Xn-1的越大那么乘以y越大,所以我們只需求出,然后ΔX越大的數和y越大的數相乘在除以2就是結果,通過畫圖很容易得出結論

? ? ? ? ?但是還有一個問題就是,對于i=0,i=n-1,Yi只乘以了一遍,而對于0<i<n的區間,每個Yi都乘以了兩遍

? ? ? ? ?所以在求ΔX時候,當i=0,ΔX=X1-X0,當i=n-1時,ΔX=Xn-1-Xn-2,而對于0<i<n,ΔX=Xi+1-xi-1;

? ? ? ? ?這樣就能確保每個y每個都可以被乘以了兩次。

? ? ? ? ?(對于兩邊的區間Y不僅被乘以了1次,而且是最小的兩個值放在了兩邊)

      #include<stdio.h>
      
        

#include
      
      <
      
        string
      
      .h>
      
        

#include
      
      <math.h>
      
        

#include
      
      <algorithm>


      
        using
      
      
        namespace
      
      
         std;


      
      
        const
      
      
        int
      
       MN=
      
        1100
      
      
        ;


      
      
        double
      
      
         x[MN],y[MN],r[MN];




      
      
        bool
      
       cmp(
      
        double
      
       a,
      
        double
      
      
         b)

{

    
      
      
        return
      
       a<
      
        b;

}




      
      
        int
      
      
         main()

{

    
      
      
        int
      
      
         i,j,n;

    
      
      
        double
      
      
         sum;

    
      
      
        int
      
      
         T;

    scanf(
      
      
        "
      
      
        %d
      
      
        "
      
      ,&
      
        T);

    
      
      
        while
      
      (T--
      
        )

    {

        sum
      
      =
      
        0
      
      
        ;

        scanf(
      
      
        "
      
      
        %d
      
      
        "
      
      ,&
      
        n);

        
      
      
        for
      
      (i=
      
        0
      
      ;i<n;i++
      
        )

           scanf(
      
      
        "
      
      
        %lf%lf
      
      
        "
      
      ,&x[i],&
      
        y[i]);

        sort(x,x
      
      +
      
        n,cmp);

        sort(y,y
      
      +
      
        n,cmp);

        
      
      
        for
      
      (i=
      
        0
      
      ;i<n-
      
        1
      
      ;i++
      
        )

        {

            
      
      
        if
      
      (i==
      
        0
      
      ) r[i]=x[i+
      
        1
      
      ]-
      
        x[i];

            
      
      
        else
      
       r[i]=x[i+
      
        1
      
      ]-x[i-
      
        1
      
      
        ];

        }

        r[i]
      
      =x[i]-x[i-
      
        1
      
      
        ];

        sort(r,r
      
      +
      
        n,cmp);

        
      
      
        for
      
      (i=
      
        0
      
      ;i<n;i++
      
        )

        {

            sum
      
      +=r[i]*
      
        y[i];

        }

        printf(
      
      
        "
      
      
        %.1lf\n
      
      
        "
      
      ,sum/
      
        2
      
      
        );

    }

    
      
      
        return
      
      
        0
      
      
        ;

}
      
    

?

ZOJ 3194 Coverage(貪心)


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 黄色短视频在线播放 | 美女视频久久 | 深夜福利在线免费观看 | 国产成人一区二区三区精品久久 | 99精品在线观看 | 久久精品一区二区影院 | 午夜精品久久久 | 成人性生免费视频 | 日韩精品一区二区三区免费视频 | 国产深夜福利视频观看 | 国产亚洲一区二区麻豆 | 色五月在线视频 | 免费在线不卡视频 | 91在线公开视频 | 国产福利一区视频 | 欧美性猛交xxxx免费看久久久 | 五月婷婷开心中文字幕 | 操她视频网站 | 久久亚洲国产午夜精品理论片 | 久久精品国产亚洲麻豆小说 | 国产成人精品一区二区视频 | 久久精品只有这里有 | 涩涩精品| 97在线观看视频免费 | 日本岛国片在线观看 | 一级黄色录像免费观看 | 欧美成人26uuu欧美毛片 | 亚洲久本草在线中文字幕 | 91亚洲国产成人久久精品网址 | 国产综合欧美日韩视频一区 | 2019天天干天天操 | 亚洲精品综合久久中文字幕 | 亚洲国产九九精品一区二区 | 在线免费精品视频 | 玖玖在线资源站 | 波多野结衣一区二区三区高清在线 | 久久国产精品国产自线拍免费 | 国产真实乱子伦精品视 | 五月天色婷婷在线 | 天天操天天摸天天干 | www.国产|