Hdu5303 Delicious Apples 贪心

题目链接：

HDU5303

题意:

有一条环形的长为L的路,仓库在位置0处,

这条路上有n棵苹果树,给出每棵苹果树的位置和苹果数量,

问用 一次最多能装K个苹果的篮子   把这条路上全部苹果採回仓库最少须要走的距离

解题思路：

这条路是环形的，先把果树分为两部分,圆的左半边算一部分,圆的右半边算还有一部分

对全部苹果依据距离排序 , 用类似背包的思想,  统计左半边,右半边用 来回走（来回的长度一定小于一个圆环的周长）的方式採集完苹果所须要走的最少距离;

最后 考虑须要走一圈的情况:左边 多出k1( <K)个苹果,右边多出k2 (<k) 个苹果.

推断   来回拿k1所需走的距离+来回拿k2所需走的距离  和 圆周长L 的 大小关系就可以得出对应答案

代码:

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

#define maxn 100050

using namespace std;

int dis[maxn],cnt;

int ldis[maxn],rdis[maxn];

int cnt1,cnt2;

LL lsum[maxn],rsum[maxn];

int cmp(int a,int b)

{

    return a<b;

}

int main()

{

//    freopen("in.txt","r",stdin);

    int T,m,n,k,a,b,L;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d%d",&L,&m,&k);

        cnt=cnt1=cnt2=0;

        while(m--)

        {

            scanf("%d%d",&a,&b);

            if(a==0)

                continue;

            if((a<<1)<=L)

                for(int i=1;i<=b;i++)

                    ldis[++cnt1]=a;

            else

                for(int i=1;i<=b;i++)

                    rdis[++cnt2]=L-a;

        }

        sort(ldis+1,ldis+cnt1+1,cmp);

        sort(rdis+1,rdis+cnt2+1,cmp);

        cnt=cnt1+cnt2;

        for(int i=1;i<=cnt1;i++)            //左半边 通过来回的方式拿完

            if(i<=k) lsum[i]=ldis[i];

            else  lsum[i]=ldis[i]+lsum[i-k];

        for(int i=1;i<=cnt2;i++)            //右半边.......

            if(i<=k) rsum[i]=rdis[i];

            else  rsum[i]=rdis[i]+rsum[i-k];

        LL ans=(lsum[cnt1]+rsum[cnt2])<<1;

        k=min(k,cnt);

        int l_,r_;

        for(int i=1;i<=cnt1&&i<=k;i++)     //枚举走一圈时,左半边拿的苹果数量

        {

            l_=cnt1-i,r_=max(0,cnt2-k+i);

            ans=min(ans,L+((lsum[l_]+rsum[r_])<<1));

        }

        printf("%I64d\n",ans);

    }

    return 0;

}