锐客网

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

多校第二场 1004 hdu 5303 Delicious Apples(背包+贪心)

IT知识delicious背包多校

寸阳分阴须爱惜，休负春色与时光。这篇文章主要讲述多校第二场 1004 hdu 5303 Delicious Apples(背包+贪心)相关的知识，希望能为你提供帮助。
题目链接：
点击打开链接

题目大意：
在一个周长为L的环上。给出n棵苹果树。苹果树的位置是xi,苹果树是ai，苹果商店在0位置，人的篮子最大容量为k,问最少做多远的距离可以把苹果都运到店里
【多校第二场 1004 hdu 5303 Delicious Apples(背包+贪心)】题目分析：
首先我们能够(ˇ?ˇ） 想～，假设在走半圆之内能够装满，那么一定优于绕一圈回到起点。所以我们从中点将这个圈劈开。那么对于每一个区间由于苹果数非常少，所以能够利用belong[x]数组记录每一个苹果所在的苹果树位置，然后将苹果依照所在的位置排序，那么也就是我们知道每次拿k个苹果的代价是苹果所在的最远的位置。
所以我们记录。sum[i]就是拿第i个苹果的时候的最小代价和，利用背包的思想就是
sum[i] = sum[i-k] + d[i]
if ( i < = k )
sum[i] = d[i]
由于当最后苹果数不足k个时候。能够通过绕一圈拿走全部的苹果。所以说。最后要枚举左右这一圈拿走的苹果，然后算取最大的情况。详细看代码。有不懂的能够再评论中询问
代码例如以下：

#include < iostream> #include < cstring> #include < algorithm> #include < cstdio> #include < vector> #define MAX 100007using namespace std; typedef long long LL; int t,l,n,k; LL sum1[MAX]; LL sum2[MAX]; LL belong[MAX]; vector< int> b1; vector< int> b2; int main ( ) { scanf ( "%d" , & t ); while ( t-- ) { scanf ( "%d%d%d" , & l , & n , & k ); int m = 0; int x,a; b1.clear(); b2.clear(); for ( int i = 0; i < n ; i++ ) { scanf ( "%d%d" , & x , & a ); for ( int i = 0 ; i < a ; i++ ) belong[++m] = x; } k = min ( k , m ); for ( int i = 1 ; i < = m ; i++ ) { //cout < < belong[i] < < " "; if ( belong[i]*2 > = l ) b2.push_back ( l-belong[i] ); else b1.push_back( belong[i] ); } //cout < < endl; sort ( b1.begin() , b1.end() ); sort ( b2.begin() , b2.end() ); int len1 = b1.size(); sum1[0] = sum2[0] = 0; for ( int i = 0 ; i < len1 ; i++ ) { int id = i+1; if ( id < = k ) sum1[id] = b1[i]; else sum1[id] = b1[i] + sum1[id-k]; } int len2 = b2.size(); //cout < < len1 < < " " < < len2 < < endl; for ( int i = 0 ; i < len2 ; i++ ) { int id = i+1; if ( id < = k ) sum2[id] = b2[i]; else sum2[id] = b2[i] + sum2[id-k]; } LL ans = ( sum1[len1] + sum2[len2] )*2 ; for ( int i = 0 ; i < = len1 & & i< = k; i++ ) { int m1 = len1 - i ; int m2 = ( 0 , len2 - (k-i) ); ans = min ( ans , 2*(sum1[m1]+sum2[m2])+l ); } printf ( "%I64d\n" , ans ); } }








    推荐阅读


    上一篇：CSAPP信息的表示和处理

    下一篇：Android StudioAndroid Studio 常用快捷键