首页 > Traveling
开通博客写题解
头像 不愿意透露姓名的牛油
发表于 2022-08-12 22:45:59
牛客小白月赛54 A-F A - Sum 最容易想到的思路就是拿个堆，每次找最大的两个数相加。但是这么做复杂度暴了（我不会算）。 考虑优化一下。先排个序，每次贪心的选最大的两个相加（为什么是两个呢，因为少的肯定比多的优，先加的比较少的话，就可以再多加几次）。这个过程就相当于从后往前求和，前缀和优化 展开全文
去ta的博客 赞 (15) 回复(3) 收起
头像 Zechariah
发表于 2022-08-12 21:37:23
F. Traveling Solution 构造题，注意细节。 考虑怎么样构造用的边数最少，然后如果m更大就加一些不影响任何最短路的边，如果两两连边还是不够m条就输出No。 首先考虑直接从1到n的最短路，显然必须有d[1]=d[n]=min{d[i]}d[1]=d[n]=min\{d[i]\}d[1 展开全文
去ta的博客 赞 (6) 回复(1) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”