Delicious ApplesTime Limit: 5000/3000 MS (Java/Others)Memory Limit: 524288/524288 K (Java/Others)Total Submission(s): 395Accepted Submission(s): 122
Problem Description
There are
apple trees planted along a cyclic road, which is metres long. Your storehouse is built at position on that cyclic road.The
th tree is planted at position
i
, clockwise from position
. There are
i
delicious apple(s) on the
th tree.You only have a basket which can contain at most
apple(s). You are to start from your storehouse, pick all the apples and carry them back to your storehouse using your basket. What is your minimum distance travelled?
5
9
There are less than 20 huge testcases, and less than 500 small testcases.
Input
First line:
, the number of testcases.Then
testcases follow. In each testcase:First line contains three integers,
.Next
lines, each line contains
i
.
Output
Output total distance in a line for each testcase.
Sample Input
210 3 22 28 25 110 4 12 28 25 10 10000
Sample Output
1826
Source
2015 Multi-University Training Contest 2
Recommend
wange2014|We have carefully selected several similar problems for you:53095308530753065305
题意：在一个圆上有n个苹果树，告诉苹果树的位置和每棵树上的苹果个数，还有一个容量为K的篮子，用篮子去摘苹果，起点在位置0，反复去摘直到把所有的苹果都摘回到0，问走的最短距离为多少。
思路：首先将圆一分为二，在圆形两侧能拿满的话肯定就是只走半边再回去，这样比走整圈划算，另外还要想到最后两边都不足K个了，这个时候最多需要走一个整圈，我们不知道这个整圈拿了哪几个苹果，那么就枚举K个。比赛时只是想到了贪心，最后那一部分没有枚举，另外这里的苹果进行了离散化，因为苹果总数只有1e5，大大简化了代码，自己当时写的太冗余=-=
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <string>#include <map>#include <stack>#include <vector>#include <set>#include <queue>#pragma comment (linker,"/STACK:102400000,102400000")#define pi acos(-1.0)#define eps 1e-6#define lson rt<<1,l,mid#define rson rt<<1|1,mid+1,r#define FRE(i,a,b) for(i = a; i <= b; i++)#define FREE(i,a,b) for(i = a; i >= b; i–)#define FRL(i,a,b) for(i = a; i < b; i++)#define FRLL(i,a,b) for(i = a; i > b; i–)#define mem(t, v) memset ((t) , v, sizeof(t))#define sf(n)scanf("%d", &n)#define sff(a,b) scanf("%d %d", &a, &b)#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)#define pfprintf#define DBGpf("Hi\n")typedef long long ll;using namespace std;#define INF 0x3f3f3f3f#define mod 1000000009const int maxn = 1e5+10;const int MAXN = 2005;const int N = 1005;ll Len,n,k,cnt;ll pos[maxn],dp_l[maxn],dp_r[maxn]; //dp[i]表示拿完前i个苹果要走的的距离和vector<ll>posl,posr;int main(){#ifndef ONLINE_JUDGEfreopen("C:/Users/lyf/Desktop/IN.txt","r",stdin);#endifll i,j,t;scanf("%lld",&t);ll x,num;while (t–){cnt=1;scanf("%lld%lld%lld",&Len,&n,&k);posl.clear();posr.clear();for (i=0;i<n;i++){scanf("%lld%lld",&x,&num);for (j=0;j<num;j++)pos[cnt++]=x;}cnt–;k=min(k,cnt);for (i=1;i<=cnt;i++){if (2*pos[i]<Len)posr.push_back(pos[i]);elseposl.push_back(Len-pos[i]);}sort(posl.begin(),posl.end());sort(posr.begin(),posr.end());dp_l[0]=dp_r[0]=0;for (i=0;i<(ll)posl.size();i++){if (i+1<=k)dp_l[i+1]=posl[i];elsedp_l[i+1]=dp_l[i+1-k]+posl[i];}for (i=0;i<(ll)posr.size();i++){if (i+1<=k)dp_r[i+1]=posr[i];elsedp_r[i+1]=dp_r[i+1-k]+posr[i];}ll ans=(dp_l[posl.size()]+dp_r[posr.size()])*2;for (i=0;i<=posr.size()&&i<=k;i++){ll right=posr.size()-i;ll left=max((ll)0,(ll)(posl.size()-(k-i)));ans=min(ans,(ll)Len+(dp_l[left]+dp_r[right])*2);}printf("%lld\n",ans);}return 0;}
版权声明：本文为博主原创文章，，未经博主允许不得转载。
累死累活不说，走马观花反而少了真实体验，
