HBC259244小宝VS牛妹,贪心,过关题目数组题解

一沫阳光 算法基础篇 55 0
想要检验自己的编程水平?来试试全网最全C++题库,让您在挑战中不断进步。
C,对于每个下标。i∈[1,n],存在右边界。定义数组的满意度为:得出长度为。m,问:至多执行。m次操作的情况下,数组的最小满意度是多少?

给出三个下标从  1 1 开始、长度为  n n 的正整数数组  A A, K K, C C。对于每个下标  iin[1,n] i∈[1,n],存在右边界  r_iin[i-1,n] r i ​ ∈[i−1,n],其中  r_i r i ​  满足两个要求。 要求  1 1: sum_{j=i}^{r_i}A_jle K_itimes C_i ∑ j=i r i ​ ​ A j ​ ≤K i ​ ×C i ​  。 要求  2 2: sum_{j=i}^{r_i+1}A_j>K_itimes C_i ∑ j=i r i ​ +1 ​ A j ​ >K i ​ ×C i ​  。 如果  r_i=i-1 r i ​ =i−1,默认要求  1 1 满足。如果  r_i=n r i ​ =n,默认要求  2 2 满足。显然, r_i r i ​  是唯一的。 每次操作可以选择一个下标  j j,令  C_j=C_j+1 C j ​ =C j ​ +1 。 定义数组的满意度为:得出长度为  n n 的数组  B B,其中  B_i=r_i-i+1 B i ​ =r i ​ −i+1。 设数组  B B 的最大值为  Max Max,最小值为  Min Min,满意度为  Max-Min Max−Min。 给出一个整数  m m,问:至多执行  m m 次操作的情况下,数组的最小满意度是多少?

HBC259244小宝VS牛妹,贪心,过关题目数组题解
-第1张图片-东莞河马信息技术
(图片来源网络,侵删)

标签: HBC259244小宝VS牛妹 贪心 过关题目数组题解