补丁数组证明

前言

补丁数组的证明比最多能完成排序的块要好讲多了(/ω＼)

实现

上代码

#include <cstdio> #include <algorithm> using namespace std; const int MAXN = 1e5 + 5; int l, n; int a[MAXN]; int main() { scanf("%d %d", &l, &n); for(int i = 1; i <= l; i++) scanf("%d", &a[i]); // sort(a + 1, a + 1 + l); int sum = 0, ans = 0;//小于sum的都可组成 for(int i = 1; i <= l; i++) { while(sum <= a[i] - 2 && sum < n) { sum = sum + sum + 1; ans++;//添加一个补丁sum + 1 } sum += a[i]; } while(sum < n) { sum = sum + sum + 1; ans++;//添加一个补丁sum + 1 } printf("%d", ans); return 0; }

证明

(一).当sum >= a[i] - 1时 则[0 , a[i] - 1]都可以被组成，那么用上a[i]后，可以组成的范围为

[0 , sum + a[i]]

原因：因为[0 , a[i] - 1]都可以被组成，那么在所有方案都用上a[i]后，可以组成的范围为[a[i] , sum + a[i]]，可是[0, a[i] - 1]也能被组成啊。所以组成的范围就为[0, sum + a[i]]了

(二).当sum < a[i] - 1时 我们则必须要让能组成的数(即sum) >= a[i] - 1，成为第一种情况

(因为题目中说了是有序的数列，所以用上了后面的，是无法影响[sum, a[i] - 1]的，因为a[j] > a[i] - 1(j > i)，所以我们必须在面对 困难 a[i]时，[1, a[i] - 1]必须组成)

为了使sum >= a[i] - 1，我们就得添加补丁

重点 补丁添多大？？？

要求:增添了补丁后，能满足凑出的最大的数要尽量大，且比Ta小的数，一定能被凑出来。

(1).若补丁大于sum + 1了

则sum + 1是无法被凑成的(易证)

不满足要求

(2).若补丁等于sum + 1

由(一)可知，是能满足要求的，且现在的能凑出的数的范围变为

[1, sum * 2 + 1]

(3).若补丁小于sum + 1

最后的范围一定没有(2)大，所以不用考虑

综上所述:补丁最优的方法是：补充sum + 1