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 次操作的情况下,数组的最小满意度是多少?