本文主要是介绍HDU 6709 2019中国大学生程序设计竞赛（CCPC） - 网络选拔赛 H Fishing Master (思维+贪心)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6709
题目大意：有个人又钓鱼又煮鱼，钓鱼的时候不能煮鱼，但是煮鱼的时候可以钓鱼，问最少花多少时间。
题目思路：队友直接秒杀tql，比赛的时候有点迷，变成了队友报听写，不知咋的就过了，最迷主代码..
今天下午寻思会会这题，结果自闭了..
太菜了....
回归正题，是花的时间最少可以理解成罐子空闲的时间最少，首先可以发现，唯一引发歧义的只有每次煮鱼的最后不足钓鱼时间的那一段，到底这段时间是去钓鱼呢，还是等到这次煮完放入下一条鱼后再去钓鱼呢？如果直接去钓鱼，那没钓完前不能放下一条鱼，这段时间直接凉凉，要是选择等的话，那假如下一条鱼煮的时间很短，钓鱼时间很长，那罐子还是得空半天，还不如稍微等会儿让罐子能少空会儿
所以这可咋办呢？其实非常简单。可以发现，直接去钓鱼唯一的好处就是你手里多了条鱼，这样你就可以避免没鱼可煮的尴尬，代价是你需要煮完后空一段时间。但是假如手里有好多鱼，劳资鱼多任性，即使现在开始钓鱼煮鱼结束后就差一点点就能钓上来我也不去钓，反正手里还有好多鱼，现在可以先不贪这点小便宜，所以策略就变成了，只要由于就只管等，如果没鱼咋办呢？有个优先队列，记录煮鱼最后那段不够钓一条鱼的尴尬时间，如果不够只能让之前一个小伙子吃点亏，煮完鱼空一会儿，那段不够的尴尬时间越长，想要得到一条新鱼的时间越短，然后就行了。
可以发现鱼越多越好，钓鱼时间相同，所以肯定煮鱼时间越长的排越前面越好，因为这样可以屯更多的鱼，减少让前面小伙子吃亏的可能性
以下是代码：
#include<iostream>
#include<cstdio>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define per(i,a,b) for(ll i=a;i>=b;i--)
#define ll long long
const ll MAXN = 1e5+5;
const ll MOD = 998244353;
ll n,k;
ll t[MAXN];
priority_queue<ll>q;
bool cmp(ll a,ll b){return a>b;
}
int main(){ll T;scanf("%lld",&T);while(T--){while(!q.empty())q.pop();scanf("%lld%lld",&n,&k);rep(i,1,n)scanf("%lld",&t[i]);sort(t+1,t+n+1,cmp);ll ans=k,num=1;rep(i,1,n){ans+=t[i];q.push(t[i]%k);num+=t[i]/k;if(num<i){ans+=k-q.top();q.pop();}}printf("%lld\n",ans);}return 0;
}
这篇关于HDU 6709 2019中国大学生程序设计竞赛（CCPC） - 网络选拔赛 H Fishing Master (思维+贪心)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
