首页 > 分享 > 优化策略：编程竞赛中的花儿增高算法

优化策略：编程竞赛中的花儿增高算法

花匠小妙招
2026-02-12 21:39

Codeforces Round #262 (Div. 2)
date：2021/11/08

题目大意：

小海狸是一个初级程序员，所以信息学是他最喜欢的科目。很快他的信息学老师就要过生日了，海狸决定为她准备一份礼物。他在窗台上种了一排花，共n朵。开始等待它们长大。然而，过了一段时间，海狸发现花停止生长了。海狸认为赠送小花是不礼貌的。所以他决定想出一些解决办法。离生日还有m天。第i朵花的高度(假设这一行花从左到右从1到n编号)此时等于ai。在剩下的几天里，海狸每天都要给相邻的w朵花浇水(一天只能浇一次)。在那一天，每朵浇水的花都生长一个高度单位。最后，海狸希望最小的花的高度尽可能大。他能得到的最小的花的最大高度是多少?

题意：

m天内，每天可以选择相邻w个花高度加1，m天后输出花中最小值的最大值； 1 思路：

考虑二分答案，check方案是： cnt = 0记录天数，每次遍历一次数组，遇到 a[i] < mid , 让 a[i] 到 a[i+w-1] 均 +1 ，直到a[i] == mid ，cnt 加变化天数， a[i] >= mid 跳过；
最后比较 cnt 与 m；

bool check(ll mid){ vector<int> b(n+1); forr(i,1,n) b[i] = a[i]; ll cnt = 0; forr(i,1,n){ if(b[i] >= mid) continue; if(mid - b[i] > m) return false; while(b[i] < mid){ cnt++; for(int j = i; j <= i+w-1 && j <= n;j++) b[j]++; } } if(cnt > m) return false; return true; }

cpp

运行

12345678910111213141516

上述check 是对思路的暴力，T8；

所以考虑优化：上面T的原因在于 check 在 n 与 w 到达最大数据量是会是O(n2)O(n^2)O(n2)级别显然会T；
如何优化呢？考虑到时间复杂度主要是来自在对w范围的增加操作，如何操作变为O(1)O(1)O(1),
开一个 b 数组来记录每个数的变化量，数的变化量主要来自前w的那个数的++操作，这样就可以不用
每次都要循环一次，详细看code；

code

/* author:@bzdhxs date:2021// URL: */ #include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<cstring> #include<string> #include<vector> #include<map> #include<queue> using namespace std; #define _orz ios::sync_with_stdio(false),cin.tie(0) #define mem(str,num) memset(str,num,sizeof(str)) #define forr(i,a,b) for(int i = a; i <= b;i++) typedef long long ll; const int N = 1e5+10; int n,m,w; int a[N]; bool check(int mid){ int cnt = 0; vector<int> b(n+1,0); int t = 0;// 由w产生的变化量，记录的一场循环的变化; forr(i,1,n){t -= i - w >= 1?b[i-w]:0;if(a[i]+t < mid){b[i] = mid - a[i] - t;// 即使天数;cnt += b[i]; // 后面和 m 比较;t += b[i]; // 变化量;}if(cnt > m) return false; } return true; } int main() { scanf("%d %d %d",&n,&m,&w); forr(i,1,n) cin >> a[i]; int l = 0, r = 1e9+100000; while(l < r){ int mid = (l+r+1) >> 1; if(check(mid)) l = mid; else r = mid - 1; } printf("%dn",r); return 0; }

cpp

运行

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051

这里对

t -= i - w >= 1?b[i-w]:0;

cpp

运行

解释：就是说t是一次循环的全局改变量；
比如说 w = 3 ， i = 1 ++ 会使 [1, 3] 每个数都++ ，t是记录全局该变量的当 i = 4 时已经不属于[1,3]内
故需要 t 减去 [1,3] 内增加的值；