首页 > 其他分享 >24/03/20 贪心(一)

24/03/20 贪心(一)

时间:2024-03-20 13:47:22浏览次数:25  
标签:24 03 20 sum dots 操作 代价 节点 pm

(1) CF1684D Traps

有 \(n\) 个数字 \(a_1 \sim a_n\) 排成一排,你需要从左到右依次越过所有数。

两种越过 \(i\) 的方式:

  1. 花费 \(a_i\) 的代价越过;
  2. 花费 \(0\) 的代价越过,后面的 \(a_i\) 都加 \(1\)。

现在你拥有最多 \(k\) 次操作二的机会,求最小的代价总和。


一定会使用 \(k\) 次操作二。否则可以在最后一个使用操作一的位置改用操作二,使答案更优。

假设这 \(k\) 次操作二的地方为 \(i_1, i_2, \dots, i_k\),我们考虑其中一个位置 \(i_j\) 的收益(收益指在 \(i_j\) 位置由操作一改为操作二后答案会变小多少):

  • 本身的代价 \(a_{i_j}\) 变成了 \(0\),收益增加 \(a_{i_j}\)。
  • 位置 \(i_j + 1 \sim n\) 中,除了位置 \(i_{j + 1}, i_{j + 2}, \dots, i_{k}\),代价都会加一(因为它们在跳跃时代价都是 \(0\)),收益减少 \(n - i_j - (k - j)\)。

综上,总收益为:

\[\sum_{j=1}^k (a_{i_j} - n + i_j + k - j) \]

整理得:

\[-nk + k^2 - \frac{k(k+1)}2 + \sum_{j=1}^k(a_{i_j} + i_j) \]

显然我们希望让收益越大越好,所以我们得目标是最大化这个式子的值。

其中 \(-nk + k^2 - \frac{k(k+1)}2\) 为定值,我们希望最大化 \(\sum_{j=1}^k(a_{i_j} + i_j)\)。所以我们将所有值按照 \(a_i + i\) 排序并取前 \(k\) 大即可。

(2) CF1029E Tree with Small Distances

给定一颗 \(n\) 个节点的树,以 \(1\) 为根。

求最少在树中加几条边,使得任意一点到 \(1\) 的距离均小于等于 \(2\)。


不难发现最优策略中,每条加的边都有端点 \(1\)。

第一步,最自然的想法就是将 \(1\) 和最深的叶节点连边。其实不然,最优的策略是连接 \(1\) 和叶子节点的父亲。这样能把这个叶子节点的所有兄弟和它父亲的父亲都管控到。

接下来上一步的点就不需要考虑了。我们要做的仍然是连接 \(1\) 和最深的点的父亲。如此迭代即可。

实现上,我们可以维护大根堆,以节点的深度从大到小排序。每次取出堆顶即可。

(3) CF1197C Array Splitting

给出一个长度为 \(n\) 的严格单调增的序列,将其分成 \(k\) 段,使得每一段的极差的和最小,求这个最小的和。


推式子。

若这 \(k\) 段分别为 \([i_1, i_2 - 1], [i_2, i_3 - 1], \dots, [i_k, i_{k + 1} - 1]\),其中 \(i_1 = 1, i_{k + 1} = n + 1\)。那么极差和为:

\[a_{i_2 - 1} - a_{i_1} + a_{i_3 - 1} - a_{i_2} + a_{i_4 - 1} - a_{i_3} + \dots + a_{i_{k + 1} - 1} - a_{i_k} \]

整理一下,把 \(+a_{i_j - 1}\) 和 \(-a_{i_j}\) 放在一起:

\[-a_{i_1} + a_{i_{k+1} - 1} + (a_{i_2 - 1} - a_{i_2}) + (a_{i_3 - 1} - a_{i_3}) + \dots + (a_{i_k - 1} - a_{i_k}) \]

其中 \(-a_{i_1} + a_{i_{k+1} - 1}\) 即 \(a_n - a_1\) 是一定的。我们希望让这个式子的值最小,就意味着我们要最小化 \((a_{i_2 - 1} - a_{i_2}) + (a_{i_3 - 1} - a_{i_3}) + \dots + (a_{i_k - 1} - a_{i_k})\)。因此求 \(d_i = a_{i - 1} - a_i\) 的前 \(k - 1\) 小即可。

(3) CF1038D Slime

给定 \(n\) 个数 \(a_i\)。每次可以选择两个相邻的 \(a_i, a_{i + 1}\) 将其合并为 \(a_i - a_{i + 1}\) 或 \(a_{i + 1} - a_i\)。求 \(n - 1\) 次操作后的数的最大值。


多手玩几组可以发现,最终的答案一定是对每个 \(a_i\) 乘上 \(\pm 1\) 的系数后求和。因为题目的操作为 \(a_i - a_{i + 1}\) 或 \(a_{i + 1} - a_i\),也就是将相邻两个数分别乘上 \(\pm 1\)。

所以我们可以对于每个负数乘 \(-1\) 变成正数,正数乘 \(1\) 保持正数,再求和即为答案。其实就是每个数的绝对值之和。

注意会有一个问题。将每个 \(a_i\) 乘 \(\pm 1\) 的过程中,不能做到将所有 \(a_i\) 全部乘相同的系数。所以在所有 \(a_i\) 同号时贪心选择某个数乘另外一个系数即可。

(4) CF804A Find Amir

有一张 \(n\) 个节点的完全图,其中连接 \(i, j\) 两点的边的边权为 \((i + j) \bmod (n + 1)\)。求走完所有城市所需的最小花费(起点任选)。


方案是 \(1 \to n \to 2 \to (n - 1) \to 3 \to \dots\),边权分别为 \(0, 1, 0, 1, \dots\)。

所以答案为边数的一半,即 \(\left \lfloor \dfrac {n-1}2 \right \rfloor\)。

标签:24,03,20,sum,dots,操作,代价,节点,pm
From: https://www.cnblogs.com/2huk/p/18085018

相关文章

  • 2024年天梯成信校赛
    2024年天梯成信校赛L1-1代码胜于雄辩-2024年天梯成信校赛补题(pintia.cn)就用PHPNoPHPcanbeusedinthiscontestsL1-2收水费-2024年天梯成信校赛补题(pintia.cn)#include<bits/stdc++.h>#definedebug(a)cout<<#a<<"="<<a<<'\n';using......
  • 掌握Go语言:Go语言通道,并发编程的利器与应用实例(20)
    通道(Channel)是用来在Go程序中传递数据的一种数据结构。它是一种类型安全的、并发安全的、阻塞式的数据传输方式,用于在不同的Go协程之间传递消息。基本概念创建通道:使用make()函数创建一个通道。ch:=make(chanint)//创建一个整型通道发送数据:使用<-操作符向通......
  • L2-032 彩虹瓶
    纯模拟,一次就AC了。#define_CRT_SECURE_NO_WARNINGS#include<bits/stdc++.h>usingnamespacestd;vector<int>huoja;//货架queue<int>order;//发货顺序intmain(){ intn,m,k;//颜色数量货架容量发货顺序 cin>>n>>m>>k; while(k--){ h......
  • 华为OD机试真题-推荐多样性-2024年OD统一考试(C卷)
    题目描述:推荐多样性需要从多个列表中选择元素,一次性要返回N屏数据(窗口数量),每屏展示K个元素(窗口大小),选择策略:1. 各个列表元素需要做穿插处理,即先从第一个列表中为每屏选择一个元素,再从第二个列表中为每屏选择一个元素,依次类推2. 每个列表的元素尽量均分为N份,如果不够N个,也......
  • 01-java面试题-----java基础——20题
    文章目录<fontcolor="red">1、java语言有哪些特点:<fontcolor="red">2、面向对象和面向过程的区别<fontcolor="red">3、标识符的命名规则。<fontcolor="red">4、八种基本数据类型的大小,以及他们的封装类<fontcolor="red">5、instanceof关键字的作用......
  • CAD学习日志-003
    *******************************************************/ 保存默认自动保存间隔是10分钟(可改),自动创建备份副本。一般保存为2007的一个版本。向上兼容,便于交流。*******************************************************/ 加密20版本以上,可以保存为一个压缩包,然后对......
  • 2024年是否是人形机器人的元年 —— 继OpenAI/Google/特斯拉之后黄仁勋也宣布NVIDIA公
    相关:https://www.youtube.com/watch?v=bMIRhOXAjYk......
  • [HAOI2007][洛谷P2218]覆盖问题
    看到这道题,思考一下后发现要用二分答案。所以为什么要用二分?因为标签有二分还在二分专题里因为对于\(ans\)来说,如果\(ans\)不行,那么\(ans-1\)也一定不行;也就是说,答案满足单调性,所以可以二分;也是因为暴力明显过不了那么对于平面上的一些点来说,如果我们用一个最小的矩形......
  • 蓝桥杯进阶03——光温显示综合应用
    一、分模块1.led和smg检测单片机上电后,8个LED灯从左到右依次点亮,然后再从左到右依次熄灭,进行LED的检测;8个数码管从左到右,逐个数码管全部段码点亮,然后再从左到右,这个数据管全部段码熄灭,进行数码管的检测。关闭蜂鸣器和继电器等无关设备。voidDisplaysmg(){ unsigned......
  • B3927 [GESP202312 四级]小杨的字典(入门小白版)
    本题包括:1.简单的map使用2.字符串简单处理本题参考洛谷题解: https://www.luogu.com.cn/problem/solution/B3927难度:普及-对于笔者而言:不会用map,在b站和csdn上搜map的使用方法,只能说是杂而乱杂在于:介绍的种类方法多种多样,但是底下的使用方法寥寥无几,与开头的介绍有......