「贪心」排队打水

题面链接

排队打水

题解

弱化版排队接水,证明稍微复杂一点

简单的贪心题,主要讲贪心证明

由题意可得我们有集合 $N = {T_1, T_2, T_3, … ,T_n}$,并且此次不是单线程,是多线程工作

于是在不考虑最优的情况下,我们可以推出得到通往结果的方程

$ans = (T_1 + T_2 + T_3 + … + T_m + (T_1 + T_{m + 1}) + (T_2 + T_{m + 2}) + (T_3 + T_{m + 3}) + … + (T_m + T_{m + m}) + (T_1 + T_{m + 1} + T_{m + m + 1}) + … + (T_j + T_{j + m} + T_{j + m + m} + … + T_{n - m} + T_{n}))$

根据贪心的子问题划分我们可以将以上式子理解为

使 $T_1$ 最优, 使 $T_2$ 最优, 使 $T_3$ 最优, … , 使 $(T_1 + T_{m + 1})$ 最优, … ,使 $(T_j + T_{j + m} + T_{j + m + m} + … + T_{n - m} + T_{n})$ 最优

所以我们每次保证 $T_i$ 在当前可数数中是最小的即可

于是根据上述分析,我们就很显然可得出代码了

我们再证明一下这个贪心策略是否正确

设当前$n = 4, m = 2$

那么我们就有集合 $N = {T_1, T_2, T_3, T_4}$ {$T|T_1 < T_2 < T_3 < T_4, T∈R$}

∴ $ans = (T_1 + T_2 + (T_1 + T_3) + (T_2 + T_4))$

那么会不会出现 $ans = (T_1 + T_2 + (T_1 + T_3) + (T_1 + T_4))$ 呢?

答案是:否 因为这样就要满足 T1 + T3 < T2,但是由于 T3 > T2 ,所以不存在这样的分支

同理 $ans = (T_1 + T_2 + (T_2 + T_3) + (T_2 + T_4))$ 也不存在

假设当前 $ans$ 非最优解,那么必定存在一个 $ans_i$ 满足 $ans_i < ans$

假设另外这个 $ans_i$ 的集合为 $N_i = {T_2, T_1, T_3, T_4}$

∴ $ans_i = (T_2 + T_1 + (T_2 + T_3) + (T_1 + T_4))$

∵ 很显然通过上面两式我们发现 $ans_i = ans$ 但其实不然 根据上述式子我们可以很容易的推出如$n = 5$ 那么

$ans = (T_1 + T_2 + (T_1 + T_3) + (T_2 + T_4) + (T_1 + T_3 + T_5))$

$ans_i = (T_2 + T_1 + (T_2 + T_3) + (T_1 + T_4) + (T_2 + T_3 + T_5))$

∵ $T_1 < T_2$ 所以 $ans < ans_i$,原假设不成立,$ans$为最优解

∴ 该贪心策略成立

「所用方法 邻项交换法

代码

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
//#define fre yes

#include <cstdio>
#include <iostream>
#include <algorithm>

const int MAXN_INT = 1005;
int arr[MAXN_INT];

int main() {
static int n, m;
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &arr[i]);
}

std::sort(arr + 1, arr + 1 + n);

int ans = 0, cnt, tot;
for (int i = 1; i <= m; i++) {
cnt = 0, tot = 0;
for (int j = i; j <= n; j += m) {
cnt += arr[j];
tot += cnt;
} ans += tot;
} printf("%d\n", ans);
return 0;
}
0%