HDU 5303 Delicious Apples(贪心)

题意:

$给定L\le 10^9的环形路,家在0号点,N\le 10^5颗苹果树,每棵有A_i个苹果,\sum A_i \le 10^5$
$现有一个K\le 10^5的篮子,求从家出发把所有的苹果装回家的最短路程$

分析:

$首先可以发现,肯定是先把近的苹果先拿走,如果拿了远的再拿近的再拿远的路程会交叉,就不优了$
$其次再考虑会不会可能走一圈,发现是可以的,见下图:$

$设起点到a的距离为l_1,到b的距离为l_2,且l_1, l_2 > {L\over 4}, A_a+A_b\le k$
$那么走一圈的路程是L,直接从最近的拿是2(l_1+l_2) > L,此时显然走一圈更优$
$更可以得出l_1,l_2\le {L\over 4}直接拿比较好$
$问题来了,可不可能走多圈呢,还是上面的图,看2圈的情况:$
$不过设A_a = x < k, A_b = k + y, 且A_a+A_b \le 2k$
$显然如果两边都是k的话,就不能绕圈了,所以可能走2圈一定是这样的$
$直接拿的话是2(l_1+2l_2)>{3L\over 2},走2圈是2L,走1圈+先拿k是L+2l_2$
$显然走2圈最差,其次L+2l_2 - (2(l_1+2l_2))=L - (2(l_1+l_2)) < 0,走1圈+先拿k最优$
$显然更多圈的情况其实都可以规约到2圈的情况$
$由于苹果个数10^5,把苹果分开看,l[i]:=左边拿i个苹果的代价,r[i]同理$
$所以问题解决了,只要枚举最后一次2边拿的让它走1圈就好了$
$时间复杂度因为有排序所以是O(nlogn)$

代码:

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
55
56
57
58
59
60
61
//
// Created by TaoSama on 2016-03-18
// Copyright (c) 2016 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>
using namespace std;
#define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
int L, n, k;
typedef long long LL;
int main() {
#ifdef LOCAL
freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
// freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
ios_base::sync_with_stdio(0);
int t; scanf("%d", &t);
while(t--) {
scanf("%d%d%d", &L, &n, &k);
vector<LL> l(1, 0), r(1, 0); //l[0] = r[0] = 0
for(int i = 1; i <= n; ++i) {
int x, y; scanf("%d%d", &x, &y);
while(y--) {
if(x << 1 < L) l.push_back(x);
else r.push_back(L - x);
}
}
sort(l.begin(), l.end());
sort(r.begin(), r.end());
for(int i = k; i < l.size(); ++i) l[i] += l[i - k];
for(int i = k; i < r.size(); ++i) r[i] += r[i - k];
LL ans = l.back() + r.back() << 1;
for(int i = 0; i <= k; ++i) {
int a = max(0, (int)l.size() - 1 - i);
int b = max(0, (int)r.size() - 1 - (k - i));
ans = min(ans, L + (l[a] + r[b] << 1));
}
printf("%I64d\n", ans);
}
return 0;
}


1. 除非注明,本博文即为原创,转载请注明链接地址
2. 本博文只代表博主当时的观点或结论,请不要恶意攻击
3. 如果本文帮到了您,不妨点一下 下面分享到 按钮,让更多的人看到