厦门网站建设手机版,线上销售模式有哪些,互联网公司介绍文案,北京住房与城乡建设部网站AcWing 102. 最佳牛围栏
1、问题
2、分析
#xff08;1#xff09;暴力做法
看到这道题以后#xff0c;我们可以先想一个最暴力的做法#xff0c;就是我们去枚举所有长度至少为 F F F的区间#xff0c;然后求出这个区间的和#xff0c;再求出这个区间的平均值。最后在…AcWing 102. 最佳牛围栏
1、问题
2、分析
1暴力做法
看到这道题以后我们可以先想一个最暴力的做法就是我们去枚举所有长度至少为 F F F的区间然后求出这个区间的和再求出这个区间的平均值。最后在这些平均值之间取一个最大值。
那么这个暴力做法的时间复杂度是多少呢枚举所有符合长度要求的区间该过程在最坏条件下的复杂度是 O ( n 2 ) O(n^2) O(n2)求出区间的和复杂度是 O ( n ) O(n) O(n)。那么总的时间复杂度就是 O ( n 3 ) O(n^3) O(n3)。
很明显这个做法是超时的那么对于这个暴力的做法我们可以给出一个小小的优化即我们通过前缀和算法将求区间的时间复杂度优化到 O ( 1 ) O(1) O(1)优化后该做法的时间复杂度是 O ( n 2 ) O(n^2) O(n2)。优化后依旧是超时的。
2二分答案前缀和DP
受朴素做法的启发我们先求一下前缀和将前缀和数组记作 s [ i ] s[i] s[i]。
这道题我们可以换个思路想假设给你一个平均值 x x x。我们要做的是判断这个平均值是否能够达到。
换句话说我们就是要判断是否存在一个区间使得这个区间和的平均值达到了 x x x。
将其转化为数学表达式即
是否存在一个区间 [ i , j ] [i,j] [i,j]其中 i − j 1 F i-j1F i−j1F满足 s [ i ] − s [ j − 1 ] i − j 1 ≥ x \frac{s[i] - s[j - 1]}{i-j1} \geq x i−j1s[i]−s[j−1]≥x 等价于 s [ i ] − s [ j − 1 ] ≥ x ∗ ( i − j 1 ) s[i] - s[j - 1] \geq x * (i-j1) s[i]−s[j−1]≥x∗(i−j1) 等价于 a [ j ] a [ j 1 ] . . . a [ i ] ≥ x x . . . x a[j]a[j1]...a[i]\geq xx...x a[j]a[j1]...a[i]≥xx...x 等价于 ( a [ j ] − x ) ( a [ j 1 ] − x ) . . . ( a [ i ] − x ) ≥ 0 (a[j]-x)(a[j1]-x)...(a[i]-x)\geq 0 (a[j]−x)(a[j1]−x)...(a[i]−x)≥0
如果我们设 b [ i ] a [ i ] − x b[i]a[i]-x b[i]a[i]−x b [ i ] b[i] b[i]的前缀和数组为 T [ i ] T[i] T[i]的话
上述式子即可转化为 T [ i ] − T [ j − 1 ] ≥ 0 T[i]-T[j-1]\geq0 T[i]−T[j−1]≥0
如果想要找到这样一个合法区间我们只需要找到一个平均值最大的区间看看它是否到达 x x x即可。
因此我们可以枚举区间右端点 i i i即固定 T [ i ] T[i] T[i]要想让 T [ i ] − T [ j − 1 ] T[i]-T[j-1] T[i]−T[j−1]最大只要找到最小的 T [ j − 1 ] T[j-1] T[j−1]即可。该过程可以用 D P DP DP来做。
这个 D P DP DP比较简单定义 d p [ i ] dp[i] dp[i]为前 i i i个 T [ i ] T[i] T[i]中最小的一个。
转移方程为 d p [ i ] m i n ( d p [ i − 1 ] , T [ i ] ) dp[i] min(dp[i-1],T[i]) dp[i]min(dp[i−1],T[i])
那么我们的 T [ i ] − T [ j − 1 ] T[i]-T[j-1] T[i]−T[j−1]的最大值即 T [ i ] − d p [ i − F ] T[i]-dp[i-F] T[i]−dp[i−F]
因为我们是枚举的 i i i所以这个过程是 O ( n ) O(n) O(n)的。
也就是说我们只需要通过 O ( n ) O(n) O(n)的时间复杂度就能够判断一个平均值 x x x是否能够达到。
因此我们只需要去二分这个 x x x即可即二分答案。
而通过题目我们发现 x x x的最大值就是2000。
因此总的时间复杂度就是 O ( n l o g ( 2000 ) ) O(nlog(2000)) O(nlog(2000))
3、代码
#includebits/stdc.h
#define endl \n
#define deb(x) cout #x x \n;
#define INF 0x3f3f3f3f
using namespace std;
const int N 1e5 10;
const double eps 1e-5;
int n, f;
double a[N], T[N], dp[N];bool check(double mid)
{for(int i 1; i n; i )T[i] T[i - 1] a[i] - mid;for(int i 1; i n; i ){dp[i] min(dp[i - 1], T[i]);}for(int i f; i n; i ){if(T[i] - dp[i-f] 0)return true;}return false;
}void solve()
{cin n f;for(int i 1; i n; i )cin a[i];double l 0, r 2000.0;while(r - l eps){double mid (l r) / 2.0;if(check(mid))l mid;elser mid;} cout (int)(r * 1000) endl;
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t 1;//cin t;while(t--)solve();
}
