盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
  4. 代码
  5. 更新日志

HDU 5303 Delicious Apples(贪心+背包)

题目

源地址:http://acm.hdu.edu.cn/showproblem.php?pid=5303

题意

有一个长度为L的圆形场地,有n种苹果树,每种苹果树距离原点距离为xi,有ai个苹果。现在有人从原点开始摘苹果,篮子最多装k个苹果,且每次摘完之后必须回到原点才能清空篮子。问他最少需要走多少距离。
保证总的苹果小于等于10^5

思路

如果从中点断开,把圆分成两半,则两边的贪心取,然后折道返回,可以得到解。但是这不是最优解,有可能最后剩下一些苹果,一次性绕一个圆形取完。可以发现,最多只能绕一圈。但是发现这个结论之后,还是不好处理。一个巧妙的想法是:
把每一个苹果当做一个点,分成左右两部分,然后分别处理。举左边一半为例,以sum[i]表示把前i个苹果全部取回的最小代价,则有:
sum[i] = di
sum[i] = sum[i - k] + di
之后枚举需要走一圈摘的苹果(可以发现这些苹果一定是离原点最远的k个点)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#include<queue>
#define pb push_back
#define debug puts("=====================");
using namespace std;
typedef long long ll;
int t, n, k, m, l;
const int N = 1e5 + 10;
vector<int> a, b;
ll s1[N], s2[N];
void work(vector<int> &a, ll * s) {
for (int i = 0; i < a.size(); i++) {
if (i < k) s[i + 1] = a[i];
else s[i + 1] = s[i + 1 - k] + a[i];
}
}
int main () {
scanf("%d", &t);
while(t--) {
scanf("%d%d%d", &l, &n, &k);
int u, v;
a.clear();
b.clear();
m = 0;
for (int i = 0; i < n; i++) {
scanf("%d%d", &u, &v);
m += v;
if (u > l / 2) {
u = l - u;
while(v--) b.pb(u);
} else while(v--) a.pb(u);
}
sort(a.begin(), a.end());
sort(b.begin(), b.end());
work(a, s1);
work(b, s2);
ll ans = s1[a.size()] * 2 + s2[b.size()] * 2;
if (m <= k) ans = min(ans, (ll)l);
else {
for (int i = 0; i < a.size() && i <= k; i++) {
ll res = s1[a.size() - i] * 2 + s2[b.size() - (k - i)] * 2 + l;
ans = min(ans, res);
}
}
printf("%I64d\n", ans);
}
return 0;
}

更新日志

  • 14277804 2015-07-31 17:14:30 Accepted 5303 889MS 3308K 1345 B G++ SIO__Five