（2019CCPC网络赛）HDU 6709 Fishing Master 贪心

浅浅的花香味﹌ 2024-04-17 05:47 32阅读 0赞

[直接上题目链接][Link 1]  
今天打了CCPC网络赛，真的是菜到抠脚

## 题目分析： ##

#### 贪心 ####

先遍历一遍每个煮鱼时间可以抓到的鱼的数量，再求和  
预处理出每个煮鱼的时间多等一会再抓一条鱼所需的时间花费，对余数排个序，差几个鱼加多少余数即可。

###### 为什么这样是对的？ ######

第一条鱼必须拿，为了煮所有的鱼必须先拿到所有的鱼。

1.  如果煮鱼时间不需额外花费拿到鱼，直接输出煮鱼总时间+第一次抓鱼的时间。
2.  如果需要额外的时间拿鱼，不管煮鱼的顺序先后，我直接选取额外花费最少的即可，因为每次选取需额外花费拿鱼的煮鱼时间，在煮鱼的过程中至少可以额外拿到一条鱼，那么也就保证了我下一次可以煮鱼，那么这个过程就可以持续进行了。

###### 代码如下 ######

#include<stdio.h>
    #include<algorithm>
    using namespace std;
    const int MAXN=1e5+6;
    const int INF=0x3f3f3f3f;
    typedef long long ll;
    ll t,n,k;
    ll a[MAXN],d[MAXN];
    int main(){ 
        scanf("%lld",&t);
        while(t--){ 
            ll cnt=1, ans=0;
            scanf("%lld%lld",&n,&k);
            for(int i=0;i<n;++i){ scanf("%lld",a+i);ans+=a[i];d[i]=k-(a[i])%k;}
            for(int i=0;i<n;++i)cnt+=a[i]/k;
            sort(d,d+n);
            for(int i=0;i<n-cnt;++i)ans+=d[i];
            printf("%lld\n",ans+k);
        }
        return 0;
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=6709

发表评论取消回复

表情：

评论列表（有 0 条评论，32人围观）

还没有评论，来说两句吧...

相关阅读

相关 2019ccpc icpc网络赛赛后总结

现在一共打了七场网络赛每一场都让人感慨颇深第一场是ccpc在航电上打的，我知道很难打，也知道自己和别人的差距，但是也没想到差距这么大，那种高级线段树都成为了签到题，自...

浅浅的花香味﹌/ 2024年04月19日 10:14/ 0 赞/ 26 阅读

相关 Fishing Master（贪心）

roblem Description Heard that eom is a fishing MASTER, you want to acknowledge him a...

本是古典何须时尚/ 2024年04月17日 18:21/ 0 赞/ 36 阅读

相关（2019CCPC网络赛）HDU 6709 Fishing Master 贪心

直接上题目链接][Link 1] 今天打了CCPC网络赛，真的是菜到抠脚题目分析：贪心先遍历一遍每个煮鱼时间可以抓到的鱼的数量，再求和预处理...

浅浅的花香味﹌/ 2024年04月17日 05:47/ 0 赞/ 33 阅读

相关 2019 CCPC网络赛

一到网络赛，大家都是东亚之光 1001 00:23:46 solved by hl 签到枚举一下位就行了 ![ContractedBlock.gif][]

左手的ㄟ右手/ 2023年10月10日 07:49/ 0 赞/ 17 阅读

相关 2019ccpc网络赛hdu6703 array(线段树)

array [题目传送门][Link 1] 解题思路操作1是把第pos个位置上的数加上\\(10^7\\)，操作2是找到区间\[1,r\]中没有且大于k的最小的

朴灿烈づ我的快乐病毒、/ 2023年08月17日 17:21/ 0 赞/ 106 阅读

相关 2019ccpc网络赛hdu6705 path

path [题目传送门][Link 1] 解题思路先用vector存图，然后将每个vector按照边的权值从小到大排序。将每个顶点作为起点的边里最短的边存入优先

怼烎@/ 2023年08月17日 17:21/ 0 赞/ 27 阅读

相关 CCPC2019网络赛

1001：输出A&B 特判A&B=0 1007: 思路：按照题意去写，分为四个部分，只有第三部分与第一部分相反，其余都与第一部分相同所以我们以第一部分为基准，去扩

深藏阁楼爱情的钟/ 2023年08月17日 16:26/ 0 赞/ 91 阅读

相关 HDU 5842—— Lweb and String & CCPC 网络赛 1011

题意：按字母出现的顺序编号，问最长上升子序列。思路：最长为26，出现一个新的字母就加上，答案为字母的种数，无聊的题目。 code：

电玩女神/ 2022年09月25日 06:28/ 0 赞/ 17 阅读

相关 CCPC2019吉林省赛&&东北地区赛游记

Preface 第一次打正式的线下赛三天，两场热身赛两场正赛，有点累 -------------------- Day 0 一大早从大学城叫滴滴去车站，差点迟到q

深藏阁楼爱情的钟/ 2021年12月13日 13:11/ 0 赞/ 278 阅读

相关 HDU重现赛之2019CCPC-江西省赛

本人蒟蒻，5个小时过了5道，看到好几个大佬AK，%%%%%%% [http://acm.hdu.edu.cn/contests/contest\_show.php?cid=8

谁借莪１个温暖的怀抱￠/ 2021年11月29日 22:30/ 0 赞/ 276 阅读