题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5303
题意：在一个长为L的环形路径上种着一些苹果树，告诉你苹果树的位置（题目中以0~L指示坐标）及苹果树上的苹果数，现在你要采集所有的苹果（大概是你有一个容量为K的筐，你采集的苹果要装在筐里，采集完要回到坐标0的家里清空筐），问你最少需要走多少路
解：可以想象最多需要走一次整环，剩下的是走两个半环，那么分别对两个半环贪心（由于数据量较小，有很优雅的姿势~）
然后考虑走的这一次整环，由于这次整环的花费是固定的（L），那么能代替之前花费越高的（K个）越好，需要枚举这K个里面有多少个是左边的，剩下的是右边的
/*
* Problem: hdu5303 Delicious Apples
* Author: SHJWUDP
* Created Time: 2015/8/10 星期一 21:46:10
* File Name: 1006.cpp
* State: Accepted
* Memo: 贪心+枚举
*/
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm> using namespace std; int L, n, K;
vector<long long> fl, fr;//f[i]:取得前i个苹果的最小花费
int main() {
#ifndef ONLINE_JUDGE
freopen("in", "r", stdin);
//freopen("out", "w", stdout);
#endif
int T;
scanf("%d", &T);
while(T--) {
scanf("%d%d%d", &L, &n, &K);
fl.clear(); fr.clear();
fl.push_back(); //强制使得fl[0]=0;
fr.push_back(); //强制使得fr[0]=0;
for(int i=; i<n; i++) {
int a, b;
scanf("%d%d", &a, &b);
while(b--) {
if(a*<L) fl.push_back(a);
else fr.push_back(L-a);
}
}
sort(fl.begin(), fl.end());
sort(fr.begin(), fr.end());
for(int i=K; i<(int)fl.size(); i++) fl[i]+=fl[i-K];
for(int i=K; i<(int)fr.size(); i++) fr[i]+=fr[i-K];
long long ans=(fl.back()+fr.back())<<;
for(int x=; x<=K; x++) { //在左边还剩下x个，右边剩下K-x个苹果时走整圈
int a=max(, (int)fl.size()--x);
int b=max(, (int)fr.size()--(K-x));
long long tmp=(fl[a]+fr[b])<<;
ans=min(ans, L+tmp);
}
printf("%I64d\n", ans);
}
return ;
}
hdu5303