这道题贪心 背包
假设在走半圆之内能够装满，那么一定优于绕一圈回到起点。所以我们从中点将这个分开，那么对于每一个区间由于苹果数非常少，所以能够利用pos[x]数组记录每一个苹果所在的苹果树位置，然后将苹果依照所在的位置排序，那么也就是我们知道每次拿k个苹果的代价是苹果所在的最远的位置。
最基本的是为什么这样选择是最优的结果
比方说在一条直线上
| pos | num |
|---|---|
| 1 | 4 |
| 2 | 2 |
| 3 | 3 |
| 4 | 4 |
篮子大小为6
那么我们能够选择先把位置4和位置2的带回家 花费 8
第二次 我们把位置3带回家 花费 6
第三次 我们把位置1带回家 花费2
那么总花费是 16
假设我们按顺序带呢 先带大的 比方位置4 的4个 、 位置3的2个 花费 8
然后带 位置3的1个 、 位置2的2个、位置1的3个 花费 6
最后带走 位置1的一个 花费 2
总花费是 16
我们发现并无差别 是选择的数据太水了吗
那么原理是什么呢
比方说三个连续的树上分别有 x y z 个苹果。篮子能够装k个苹果
假设 y+ z < k 那么肯定选择带走后面两个树的苹果 ，再带走第一个树的苹果 。这是最优解
假设 y+z >k &&x+z<k 呢 是不是感觉先带走第一个和第三个是最优解
我们能够看一下 带走第一个和第三个 那么总花费是 (z+(y+k-1)/k*y)*2
假设继续依照顺序从后面往前取 花费是 ( z+（y-k+z+k-1）/k*y+(x-(y-k+z)%k))*2
带入几组数 前一个式子>=后面的
那么依照顺序从后面往前取的贪心策略是正确的
注意点：最后枚举圈剩余的苹果数小于等于k时候，还有一面有可能是0，所以减得时候，有可能是负数
/* **********************************************
Auther: xueaohui
Created Time: 2015-7-25 13:19:20
File Name : D.cpp
*********************************************** */
#include <iostream>
#include <fstream>
#include <cstring>
#include <climits>
#include <deque>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <ctime>
#include <bitset>
#include <functional>
#include <algorithm>
using namespace std;
#define ll long long
#define N 111111
ll l;
int n,k;
int a[N];
ll dpx[N],dpy[N];
ll pos[N];
vector<ll>x,y;
int main(){
int T;
scanf("%d",&T);
while(T--){
x.clear();
y.clear();
memset(dpx,0,sizeof(dpx));
memset(dpy,0,sizeof(dpy));
scanf("%I64d%d%d",&l,&n,&k);
int cnt = 0 ;
int all;
ll p;
for(int i=1;i<=n;i++){
scanf("%I64d%d",&p,&all);
for(int j=1; j<=all;j++)
pos[++cnt]=p;
}
//:printf("cnt = = %d
",cnt);
for(int i=1;i<=cnt;i++){
ll pp =pos[i]*2;
if(pp<=l) x.push_back(pos[i]);
else y.push_back(l-pos[i]);
}
sort(x.begin(),x.end());
sort(y.begin(),y.end());
int xsize = x.size();
int ysize = y.size();
for(int i=1;i<=xsize;i++){
dpx[i] = (i>k)?dpx[i-k] + x[i-1]:x[i-1];
}
for(int i=1;i<=ysize;i++){
dpy[i] = (i>k)?dpy[i-k] + y[i-1]:y[i-1];
}
ll ans = dpx[xsize] + dpy[ysize];
ans *= 2;
for(int i=0;i<=k&&i<=xsize;i++){
int c = max(0,ysize+i-k);//注意点
ans = min(ans,(dpx[xsize-i] + dpy[c])*2+l);
}
printf("%I64d
",ans);
}
}