首页 > 代码库 > HDU 5303 Delicious Apples (贪心 枚举 好题)
HDU 5303 Delicious Apples (贪心 枚举 好题)
Delicious Apples
Time Limit: 5000/3000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 199 Accepted Submission(s): 54
Problem Description
There are
apple trees planted along a cyclic road, which is
metres long. Your storehouse is built at position
on that cyclic road.
The th tree is planted at position , clockwise from position . There are delicious apple(s) on the th tree.
You only have a basket which can contain at most 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?
There are less than 20 huge testcases, and less than 500 small testcases.
The th tree is planted at position , clockwise from position . There are delicious apple(s) on the th tree.
You only have a basket which can contain at most 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?
There are less than 20 huge testcases, and less than 500 small testcases.
Input
First line:
,
the number of testcases.
Then testcases follow. In each testcase:
First line contains three integers, .
Next lines, each line contains .
Then testcases follow. In each testcase:
First line contains three integers, .
Next lines, each line contains .
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
Source
2015 Multi-University Training Contest 2
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5303
题目大意:有一个长为L的环。n个苹果树,一个篮子最多装k个苹果,装完要回到起点卸下再出发。给出n个苹果树顺时针的位置及苹果的个数。求摘全然部苹果走的最小路程
题目分析:显然。仅仅有在某种特殊条件下,即两側都还有苹果且能够一次装完且最后的苹果都离起点比較远。这样的情况下。我们直接绕圈可能会更优,也就是说整圈最多绕一次。因此我们能够先对两边贪心。题目的数据显示苹果的数量最多就1e5,显然我们能够把苹果“离散”出来,用x[i]记录第i个苹果到起点的位置。然后对位置从小到大排序,先选择路程小的。选择的时候用dis[i]记录单側装了i个苹果的最小路程,类似背包计数的原理。答案要乘2,由于是来回的,最后在k>=i时。枚举绕整圈的情况,szl-i表示仅仅走左边採的苹果数,szr - (k - i)表示仅仅走右边採的苹果树。画个图就能看出来了。注意右边这里可能值为负。要和0取最大,然后答案就是(disl[szl-i] + disr[szr - (k - i)])* 2 +L,这里事实上绘图更加直观。最后取最小就可以,注意有几个wa点,一个是要用long long。二是之前说的出现负数和0取大,三是每次要清零
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5303
题目大意:有一个长为L的环。n个苹果树,一个篮子最多装k个苹果,装完要回到起点卸下再出发。给出n个苹果树顺时针的位置及苹果的个数。求摘全然部苹果走的最小路程
题目分析:显然。仅仅有在某种特殊条件下,即两側都还有苹果且能够一次装完且最后的苹果都离起点比較远。这样的情况下。我们直接绕圈可能会更优,也就是说整圈最多绕一次。因此我们能够先对两边贪心。题目的数据显示苹果的数量最多就1e5,显然我们能够把苹果“离散”出来,用x[i]记录第i个苹果到起点的位置。然后对位置从小到大排序,先选择路程小的。选择的时候用dis[i]记录单側装了i个苹果的最小路程,类似背包计数的原理。答案要乘2,由于是来回的,最后在k>=i时。枚举绕整圈的情况,szl-i表示仅仅走左边採的苹果数,szr - (k - i)表示仅仅走右边採的苹果树。画个图就能看出来了。注意右边这里可能值为负。要和0取最大,然后答案就是(disl[szl-i] + disr[szr - (k - i)])* 2 +L,这里事实上绘图更加直观。最后取最小就可以,注意有几个wa点,一个是要用long long。二是之前说的出现负数和0取大,三是每次要清零
#include <cstdio> #include <cstring> #include <vector> #include <algorithm> #define ll long long using namespace std; int const MAX = 1e5 + 5; int L, n, k; ll x[MAX], disl[MAX], disr[MAX]; vector <ll> l, r; int main() { int T; scanf("%d", &T); while(T--) { memset(disl, 0, sizeof(disl)); memset(disr, 0, sizeof(disr)); l.clear(); r.clear(); scanf("%d %d %d", &L, &n, &k); int cnt = 1; for(int i = 1; i <= n; i++) { ll pos, num; scanf("%lld %lld", &pos, &num); for(int j = 1; j <= num; j++) x[cnt ++] = (ll) pos; //离散操作 } cnt --; for(int i = 1; i <= cnt; i++) { if(2 * x[i] < L) l.push_back(x[i]); else r.push_back(L - x[i]); //记录位置 } sort(l.begin(), l.end()); sort(r.begin(), r.end()); int szl = l.size(), szr = r.size(); for(int i = 0; i < szl; i++) disl[i + 1] = (i + 1 <= k ? l[i] : disl[i + 1 - k] + l[i]); for(int i = 0; i < szr; i++) disr[i + 1] = (i + 1 <= k ? r[i] : disr[i + 1 - k] + r[i]); ll ans = (disl[szl] + disr[szr]) * 2; for(int i = 0; i <= szl && i <= k; i++) { int p1 = szl - i; int p2 = max(0, szr - (k - i)); ans = min(ans, 2 * (disl[p1] + disr[p2]) + L); } printf("%I64d\n", ans); } }
HDU 5303 Delicious Apples (贪心 枚举 好题)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。