|
905.区间选点
链接：https://www.acwing.com/problem/content/907/
给定 N 个闭区间 [ai,bi]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。
输出选择的点的最小数量。
位于区间端点上的点也算作区间内。
解法：按终点排序，每次选尽可能靠右的，某项不符合，则需要选它。
证明：上面算出来的答案为cnt，正确答案为ans。
需要证明cnt>=ans,cnt<=ans。
首先cnt这个为一个合法的方法，必定大于等于标准答案。
对于cnt<=ans，对于这类方法选择的区间，具有一个性质，区间之间必定不相交，即要想选择出这些不相交的区间，也至少需要cnt次，故证明完毕。
908.最大不相交区间数量
链接：https://www.acwing.com/problem/content/910/
给定 N 个闭区间 [ai,bi]，请你在数轴上选择若干区间，使得选中的区间之间互不相交（包括端点）。
输出可选取区间的最大数量。
解法：按终点排序，扫描所有线段，能选就选。
证明：首先，这个方法算出来的cnt必定为一种方案，且选出来的方案与上题905.区间选点一致，由于为合法方案，故ans>=cnt。接下来证明ans<=cnt，反证：如果ans>cnt，则说明可以找到ans个不相交的区间，在上题中，如果为ans个区间，则必定答案需要为>=ans个点，而上题实际不需要，矛盾了，故假设错误，ans<=cnt。
906.区间分组
https://www.acwing.com/problem/content/908/
给定 N 个闭区间 [ai,bi]，请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小。
输出最小组数。
解法：按起点从小到大排序，然后能放就放，没地方放就准备一个新组。
证明：此类方法必定为合法方法cnt，cnt>=ans，接下来证明cnt<=ans。
当按此类方法递推时，到某一刻为第cnt个组，这个区间必定与上面cnt-1个区间产生了重合，即必定有一个点出现在至少cnt个区间中，则ans>=cnt。
907.区间覆盖
https://www.acwing.com/problem/content/909/
给定 N 个闭区间 [ai,bi] 以及一个线段区间 [s,t]，请你选择尽量少的区间，将指定线段区间完全覆盖。
输出最少区间数，如果无法完全覆盖则输出 ?1。
解法：按起点从小到大，每次在可选的范围中选延伸最远的即可。
证明：对于任意一种方案ans，与我们生成的方法cnt进行对比，从左至右对比，当出现不一致时，根据我们的选择方法，必定右边界大于ans方案的边界，即可等价替换，必定也满足，即任意一种最好的答案，都可以替换成我们的cnt答案，故cnt方案即为最优答案。
148.合并果子
链接：https://www.acwing.com/problem/content/150/
经典问题，首先对于任意一种合并形态，都可以理解为一个二叉树的合并过程，且最小的两个点必定为最深点，且可以为兄弟。通过反证法：如果不为最深即可替换，必定更优，如果不为兄弟必可替换，必定答案不变。故最优答案的第一步必定为最小的两个合并，接下来变为N-1个合并，注意这里不能直接继续推这个结论。对于N-1个合并的任意一种方案，设代价为F(N-1)，即F(N)的对应方案为F(n-1)+cost，任意一种方案都可以转换为这样，都加上了cost，即要让F(N)最小，即要让F(n-1)最小，重复这个问题即可。
913.排队打水
链接：https://www.acwing.com/problem/content/description/915/
有 n 个人排队到 1 个水龙头处打水，第 i 个人装满水桶所需的时间是 ti，请问如何安排他们的打水顺序才能使所有人的等待时间之和最小？
解法：把时间按从低到高排序，依次处理即可。
反证法，如果时间不是依次递增的，则必定存在下降点，交换两个必定可以为更好，故必为递增。
104.货仓选址
链接：https://www.acwing.com/problem/content/106/
在一条数轴上有 N 家商店，它们的坐标分别为 A1～AN。
现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。
为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。
解法：中位数即可，如果为奇数，则为中间，如果为偶数，则中间两个之间都可以。
证明：最终答案为|x1-o|+|x2-o|+…+|xn-o|=(|x1-o|+|xn-o|)+(|x2-o|+|x(n-1)-o|)+…>=(xn-x1)+(x(n-1)-x2)+…，当选到中间点时，刚好为=，故为最优解。
125.耍杂技的牛
链接：https://www.acwing.com/problem/content/127/
解法：按w[i]+s[i]从小到大排序即可。
如果不是排序，则是必然存在i<i+1，w[i]+s[i]>w[i+1]+s[i+1]，sum[i]为前i个w[i]的前缀和，首先这两个的交换对其它奶牛是没有影响的，只影响这两中，这样的答案最大值为max(sum[i-1]-s[i],sum[i-1]+w[i]-s[i+1])，如果交换则为max(sum[i-1]-s[i+1],sum[i-1]+w[i+1]-s[i])。
式子全部-sum[i-1]+s[i]+s[i+1]，
上者为max(s[i+1],s[i]+w[i])后者为max(s[i],w[i+1]+s[i+1])
约简得到s[i]+w[i]与w[i+1]+s[i+1]比较，由于w[i]+s[i]>w[i+1]+s[i+1]，所以交换以后，max的答案一定变得更小。
1080 [NOIP2012 提高组] 国王游戏
链接：https://www.luogu.com.cn/problem/P1080
同上，按w[i]*s[i]从小到大排序即可。
如果不是排序，则是必然存在i<i+1，w[i]*s[i]>w[i+1]*s[i+1]，sum[i]为前i个w[i]的前缀乘积，首先这两个的交换对其它奶牛是没有影响的，只影响这两中，这样的答案最大值为max(sum[i-1]/s[i],sum[i-1]*w[i]/s[i+1])，如果交换则为max(sum[i-1]/s[i+1],sum[i-1]*w[i+1]/s[i])。
式子全部/sum[i-1]*s[i]*s[i+1]，
上者为max(s[i+1],s[i]*w[i])后者为max(s[i],w[i+1]*s[i+1])
约简得到s[i]*w[i]与w[i+1]*s[i+1]比较，由于w[i]*s[i]>w[i+1]*s[i+1]，所以交换以后，max的答案一定变得更小。
|