T1
如果 $sum[k]$是奇数,一定是最优解,因为 $w[k+1] \le w[k] \le w[k - 1] … w[1]$,替换任何一个数字,结果变成 $ans2 = sum[k] - w[i] + w[j] (i \in [1, k], j \in [k + 1, n])$,而因为 $w[i] \ge w[j]$,所以 $ans2 \le ans$,所以 $ans$ 此时一定是最优解。
如果 $sum[k]$是偶数,按照贪心的做法,一定是得到最优解的。
首先证明正确性:
设$a,b,c,d$分别是$[1,k]$中最小的奇数、偶数,$[k+1,n]$中最大的奇数、偶数。
因为偶数+奇数=奇数,偶数+偶数=偶数,所以当且仅当在$[1,k],[k+1,n]$中存在一对奇偶性不同的数,才能使$ans$变成一个奇数,才有解。
因为最大的奇数一定是奇数……所以正确性得证。
接着证明最优性:
$ans2 = ans - t, t = w[j] - w[i]$。
容易发现 $t$随着$w[i]$的增大而减小,随着$w[j]$的增大而增大。
当$w[j]$最小,$w[i]$最大时,取得最大值。
而题目要求的就是最大值,最优性得证。
证毕。
T2
将题解的两个步骤统一起来:
首先将 $t$ 数组从大到小排序;
对于任何一个$t_i$,选择目前总和最小的一个序列,加入进去;
所有序列和的最大值就是答案(最多 $m$ 个序列)。
假设这么贪心是错误的,我们从前往后找到第一个错误的操作。
此时队列如下。
一般的,设当前加入的$t[i]=x$,加入序列的长度是 $y$,其它任意一个序列上面最后加入的$t[j]=a$,剩下的长度是 $b$。
根据贪心,有 $x + y \ge a + b, b \ge y , x \ge a + b$。
因为假设贪心是错误的,所以正确的方法一定是错误的一步交换一下位置,上面的情况,交换之后$y + a \le b + x$,而 $b + x \ge x + y$,所以一定不会更优。
贪心就是正确的,大概理解吧……