锐客网

  1. 首页 > 睿知 > it技术 > >

Hdu5303Delicious Apples贪心

IT知识贪心deliciousapple

落花踏尽游何处，笑入胡姬酒肆中。这篇文章主要讲述Hdu5303Delicious Apples贪心相关的知识，希望能为你提供帮助。
题目链接：
【Hdu5303Delicious 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]; elselsum[i]=ldis[i]+lsum[i-k]; for(int i=1; i< =cnt2; i++)//右半边....... if(i< =k) rsum[i]=rdis[i]; elsersum[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; }















    推荐阅读


    上一篇：事件处理安卓4——单击事件

    下一篇：关于游戏打包(Android)后，手机上的模型贴图显示模糊问题的解决方案