程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 5037 Frog(貪心)

hdu 5037 Frog(貪心)

編輯:C++入門知識

hdu 5037 Frog(貪心)


分析:貪心吧,讓每次跳的點盡量小。

石頭是可能無序的,比賽是實在沒發現,就加了個排序過了,哎。。。

和代碼一起講做法吧,假設情況1 :上一步k加這一步余數x大於L,則最後剩余部分需要單獨跳;情況2:上一步k加這一步余數x小於等於L,最後剩余部分可以並進上一步,即k+x。

畫了一張圖http://my.csdn.net/my/album/detail/1786547

代碼:

#include
#include
#include
#include
#include
#include
#include
#include
#define MOD 1000000007
typedef long long ll;
using namespace std;

const int maxn=200005;
int da[maxn];

int main()
{
    int T,n,m,l,cas=0;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&n,&m,&l);
        for(int i=1;i<=n;i++)
            scanf("%d",&da[i]);
        da[++n]=m;da[0]=0;

        int ans=0;
        int k=l;//k表示上次跳的距離,用此限制下次的跳越
        sort(da,da+n);
        for(int i=1;i<=n;i++)
        {
            int x=(da[i]-da[i-1])%(l+1);
            int y=(da[i]-da[i-1])/(l+1);
            if(k+x>=l+1)
            {
                k=x;
                ans+=y*2+1;
            }
            else if(k+x

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved