简阳网站建设简阳,wordpress免费常用插件,做网站哪家公司专业,网站运营团队各岗位的职责是什么题目#xff1a;最佳牛围栏
题目链接#xff1a;https://www.acwing.com/problem/content/104/
题意#xff1a;农夫约翰的农场由 N 块田地组成#xff0c;每块地里都有一定数量的牛#xff0c;其数量不会少于 1 头#xff0c;也不会超过 2000 头。 约翰希望用围栏将一…题目最佳牛围栏
题目链接https://www.acwing.com/problem/content/104/
题意农夫约翰的农场由 N 块田地组成每块地里都有一定数量的牛其数量不会少于 1 头也不会超过 2000 头。 约翰希望用围栏将一部分连续的田地围起来并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。 围起区域内至少需要包含 F 块地其中 F 会在输入中给出。 在给定条件下计算围起区域内每块地包含的牛的数量的平均值可能的最大值是多少
思路 找平均值/最小大值的最大小值往二分答案方向想二分答案的模板见代码。我们在每一次假设答案的计算过程中将数组都减去mid方便计算也就是只要存在满足条件同时大于0的字段就可以返回true了 因为是找连续的一段我们用前缀和优化计算假设前缀和数组为pre只要存在pre[j]-pre[i]0且j-if就可以返回true了。
#includebits/stdc.husing namespace std;using ll long long;
const ll N 100005;
const ll mod 1e9 7;
const int maxn 2005;
int gcd(int a, int b) {return b ? gcd(b, a % b) : a;
}int n, f;
int a[N];
double pre[N];bool check(double m) {for (int i 1; i n; i) {pre[i] pre[i - 1] a[i] * 1.0 - m;}double minn 0;for (int i 0, j f; j n; j, i) {minn min(minn, pre[i]);if (pre[j] minn)return true;}return false;
}void solve() {cin n f;for (int i 1; i n; i) {cin a[i];}double l 1, r 2002;while (r-l1e-5) {double mid (l r) / 2;if (check(mid)) {l mid;}elser mid;}cout (int)(r * 1000) \n;}signed main() {ios::sync_with_stdio(false);cin.tie(0);std::cout.tie(0);int t 1; //cin t;while (t--)solve();return 0;
}
