Zth's Blog

记录学习路上的点滴

0%

cf792d 贪心

题目链接

题目

题目描述

给你$n$个数$a_1, a_2, … a_n$, 你要从$1$到$n$选数, 你最多有$k$次机会可以跳过一个数不选它, 但是后面的数权值会$+ 1$, 形式化的

如果你跳过了$a_i$, 那么$a_{i + 1}, a_{i + 2}, a_n$都要$+ 1$

$+ 1$可以被累计, 也就是一个位置可以被加多次

最小化选出的数的和, 并输出

数据范围

$t$组数据, $1 \leq t \leq 100$

$1 \leq k \leq n \leq 2 \times 10 ^ 5, \sum n \leq 2 \times 10 ^ 5$

$1 \leq a_i \leq 10^9$

题解

dp

显然, $k$次机会一定要全用完, 因为如果我们没有用完$k$次机会, 那我们可以在当前状态从后往前找到第一个没被跳过的, 把它跳过, 答案一定会变小

我们尝试$dp$, 那么对于一个位置$i$的数我们有选和不选两种状态, 不选的话会对后续的数产生影响, 消除影响的话需要记录$1 … i$位置跳过了多少个, 所以我们设$dp[i][j]$表示选到第$i$个数, 跳过了$j$个数的方案, 那么有

由于$n \leq 2 \times 10^5$, 时空都无法接受

贪心

直觉告诉我们虽然跳过一个数有了后续的影响, 但是$a_i$的大小肯定还是有主导的, 应该可以贪心, 先设这$n$个数的和为$sum$, 初始$ans = sum$

观察可得, 对答案有影响的除了$a_i$本身的大小, 还有位置$i$, 举个例子, 如果$k$个跳过全都在最后, 那么$+1$操作就相当于没有了 。 原因在于每个数的贡献除了$a_i$, 还有$i$之后选的数的个数, 那我们尝试算上位置的贡献

考虑单个数的贡献的话, 我们不得不关注这个数后面还有几个被/没被跳过, 这个过程无从下手; 但是结果都是一样的: $k$个数被跳过了, 所以我们尝试从结果反向推理, 并且考虑整体的贡献

假设我们选出了$k$个位置的数用来跳过, 其位置分别为$p_1, p_2, … , p_k$, 那么会使答案减少$a_{p_1}, a_{p_2}, …, a_{p_k}$, 同时增加$n - p_1 - (k - 1), n - p_2 -(k - 2), … , n - p_k$, 增加的总贡献为$k \times n - \sum p - \frac{k(k - 1)}{2}$, 最终一共会使答案减少$\sum (a_p + p) - k \times n + \frac{k(k - 1)}{2}$, 式子中只有$p$是变量, 那我们只要选择$a_i + i$最大的$k$个位置跳过就好了

通过反推和计算整体贡献的方法, 我们成功消除了跳过的这些数位置之间的影响, 转换成每个位置的贡献只与自己的位置有关

感觉这个方法很巧妙, 不看题解我想不到

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <cstdio>
#include <algorithm>

int t;
int n, k;
int b[200005];
long long sum;

int main()
{
scanf("%d", &t);
while(t --)
{
sum = 0;

scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i ++)
{
int a;
scanf("%d", &a);

sum += a;
b[i] = a + i;
}

std:: sort(b + 1, b + n + 1);
std:: reverse(b + 1, b + n + 1);

for(int i = 1; i <= k; i ++) sum -= b[i];
sum += 1LL * k * n;
sum -= 1LL * k * (k - 1) / 2;

printf("%lld\n", sum);
}

return 0;
}