Problem Description
There are n apple trees planted along a cyclic road, which is L metres long. Your storehouse is built at position 0 on that cyclic road.
The ith tree is planted at position xi, clockwise from position 0. There are ai delicious apple(s) on the ith tree.
The ith tree is planted at position xi, clockwise from position 0. There are ai delicious apple(s) on the ith tree.
You only have a basket which can contain at most K 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?
1≤n,k≤105,ai≥1,a1+a2+...+an≤105
1≤L≤109
0≤x[i]≤L
There are less than 20 huge testcases, and less than 500 small testcases.
Input
First line: t, the number of testcases.
Then t testcases follow. In each testcase:
First line contains three integers, L,n,K.
Next n lines, each line contains xi,ai.
Then t testcases follow. In each testcase:
First line contains three integers, L,n,K.
Next n lines, each line contains xi,ai.
Output
Output total distance in a line for each testcase.
Sample Input
2
10 3 2
2 2
8 2
5 1
10 4 1
2 2
8 2
5 1
0 10000
Sample Output
18
26
26
题意：给一个圈，设起点为0，给出周长为L，在圈中有 n 棵树，依次给出按顺时针方向与起点的距离，树上的苹果数。给出篮子大小（最多能装的苹果树）。问最少走多远可以采集完所有苹果。
思路：
以过起点的直径为界，以苹果树在左半圆和右半圆分别贪心，得到要走的距离。最后枚举最后走一整圈所采集的苹果（详见代码）。比较得出最小值。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define maxn 100050
int d_l[maxn],d_r[maxn],l,n,k,t,x,a,L,R;
long long tot_l[maxn],tot_r[maxn],ans,tmp;
int main(){
scanf("%d",&t);
while(t--){
L=R=;
scanf("%d%d%d",&l,&n,&k);
for(int i=;i<n;i++){
scanf("%d%d",&x,&a);
for(int j=;j<a;j++){
if(x*<l) d_l[++L]=x;
else d_r[++R]=l-x;
}
}
sort(d_l+,d_l+L+);
sort(d_r+,d_r+R+);
for(int i=;i<=L;i++){
if(i<=k) tot_l[i]=d_l[i];
else tot_l[i]=tot_l[i-k]+d_l[i];
}
for(int i=;i<=R;i++){
if(i<=k) tot_r[i]=d_r[i];
else tot_r[i]=tot_r[i-k]+d_r[i];
}
ans=(tot_l[L]+tot_r[R])*;
for(int i=;i<=k;i++){
tmp=(tot_l[L-i]+tot_r[max(,R-(k-i))])*;
ans=min(ans,l+tmp);
}
printf("%I64d\n",ans);
}
return ;
}