Delicious Apples (hdu 5303 贪心+枚举)
HDU 枚举 贪心
2023-09-11 14:14:09 时间
Delicious Apples
Time Limit: 5000/3000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)Total Submission(s): 395 Accepted Submission(s): 122
Problem Description
There are n![]()
apple trees planted along a cyclic road, which is
L![]()
metres long. Your storehouse is built at position
0![]()
on that cyclic road.
Thei![]()
th
tree is planted at position x
i![]()
![]()
,
clockwise from position 0![]()
.
There are a
i![]()
![]()
delicious apple(s) on the i![]()
th
tree.
You only have a basket which can contain at mostK![]()
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?
The
You only have a basket which can contain at most
5
,a
i
≥1,a
1
+a
2
+...+a
n
≤10
5
9
There are less than 20 huge testcases, and less than 500 small testcases.
Input
First line: t![]()
,
the number of testcases.
Thent![]()
testcases follow. In each testcase:
First line contains three integers,L,n,K![]()
.
Nextn![]()
lines, each line contains x
i
,a
i![]()
![]()
.
Then
First line contains three integers,
Next
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
Recommend
题意:在一个圆上有n个苹果树。告诉苹果树的位置和每棵树上的苹果个数,另一个容量为K的篮子,用篮子去摘苹果,起点在位置0,重复去摘直到把全部的苹果都摘回到0,问走的最短距离为多少。
思路:首先将圆一分为二,在圆形两側能拿满的话肯定就是仅仅走半边再回去,这样比走整圈划算。另外还要想到最后两边都不足K个了。这个时候最多须要走一个整圈,我们不知道这个整圈拿了哪几个苹果,那么就枚举K个。
比赛时仅仅是想到了贪心,最后那一部分没有枚举,另外这里的苹果进行了离散化,由于苹果总数仅仅有1e5,大大简化了代码。自己当时写的太冗余=-=
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <string> #include <map> #include <stack> #include <vector> #include <set> #include <queue> #pragma comment (linker,"/STACK:102400000,102400000") #define pi acos(-1.0) #define eps 1e-6 #define lson rt<<1,l,mid #define rson rt<<1|1,mid+1,r #define FRE(i,a,b) for(i = a; i <= b; i++) #define FREE(i,a,b) for(i = a; i >= b; i--) #define FRL(i,a,b) for(i = a; i < b; i++) #define FRLL(i,a,b) for(i = a; i > b; i--) #define mem(t, v) memset ((t) , v, sizeof(t)) #define sf(n) scanf("%d", &n) #define sff(a,b) scanf("%d %d", &a, &b) #define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c) #define pf printf #define DBG pf("Hi\n") typedef long long ll; using namespace std; #define INF 0x3f3f3f3f #define mod 1000000009 const int maxn = 1e5+10; const int MAXN = 2005; const int N = 1005; ll Len,n,k,cnt; ll pos[maxn],dp_l[maxn],dp_r[maxn]; //dp[i]表示拿完前i个苹果要走的的距离和 vector<ll>posl,posr; int main() { #ifndef ONLINE_JUDGE freopen("C:/Users/lyf/Desktop/IN.txt","r",stdin); #endif ll i,j,t; scanf("%lld",&t); ll x,num; while (t--) { cnt=1; scanf("%lld%lld%lld",&Len,&n,&k); posl.clear(); posr.clear(); for (i=0;i<n;i++) { scanf("%lld%lld",&x,&num); for (j=0;j<num;j++) pos[cnt++]=x; } cnt--; k=min(k,cnt); for (i=1;i<=cnt;i++) { if (2*pos[i]<Len) posr.push_back(pos[i]); else posl.push_back(Len-pos[i]); } sort(posl.begin(),posl.end()); sort(posr.begin(),posr.end()); dp_l[0]=dp_r[0]=0; for (i=0;i<(ll)posl.size();i++) { if (i+1<=k) dp_l[i+1]=posl[i]; else dp_l[i+1]=dp_l[i+1-k]+posl[i]; } for (i=0;i<(ll)posr.size();i++) { if (i+1<=k) dp_r[i+1]=posr[i]; else dp_r[i+1]=dp_r[i+1-k]+posr[i]; } ll ans=(dp_l[posl.size()]+dp_r[posr.size()])*2; for (i=0;i<=posr.size()&&i<=k;i++) { ll right=posr.size()-i; ll left=max((ll)0,(ll)(posl.size()-(k-i))); ans=min(ans,(ll)Len+(dp_l[left]+dp_r[right])*2); } printf("%lld\n",ans); } return 0; }
相关文章
- 致初学者(二): HDU 2014~ 2032题解
- hdu 5077 NAND(打表)2014 Asia regional 鞍山站 H题
- [ACM] hdu 1253 胜利大逃亡 (三维BFS)
- HDU 5319 Painter(枚举)
- 2015 Multi-University Training Contest 3 hdu 5317 RGCDQ
- HDU 2476 String painter
- HDU 1199 Color the Ball
- HDU 2639 Bone Collector II
- HDU 5236 Article (概率DP+贪心)
- HDU 5546 Ancient Go (搜索)
- HDU 1270 小希的数表 (暴力枚举+数学)
- 【HDU 1003】 Max Sum
- HDU 5358 First One(枚举)
- hdu 1384 Intervals (差分约束)
- hdu 4742 Pinball Game 3D(三维LIS&cdq分治&BIT维护最值)
- 多校第六场 HDU 4927 JAVA大数类+模拟