首页 / 算法 / 《算法竞赛进阶指南》0.4二分
《算法竞赛进阶指南》0.4二分
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了《算法竞赛进阶指南》0.4二分,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2562字,纯文字阅读大概需要4分钟。
内容图文
![《算法竞赛进阶指南》0.4二分](/upload/InfoBanner/zyjiaocheng/829/0e85602364dd46d48d0db218bf1074b0.jpg)
102. 最佳牛围栏
农夫约翰的农场由N块田地组成,每块地里都有一定数量的牛,其数量不会少于1头,也不会超过2000头。
约翰希望用围栏将一部分连续的田地围起来,并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。
围起区域内至少需要包含 F块地,其中 F会在输入中给出。
在给定条件下,计算围起区域内每块地包含的牛的数量的平均值可能的最大值是多少。
输入格式
第一行输入整数 N和 F,数据间用空格隔开。
接下来 N行,每行输出一个整数,第i+1行输出的整数代表,第i片区域内包含的牛的数目。
输出格式
输出一个整数,表示围起区域内每块地包含的牛的数量的平均值可能的最大值乘以1000得到的数值。
数据范围
1≤N≤100000
1≤F≤N
输入样例:
10 6
6
4
2
10
3
8
5
9
4
1
输出样例:
6500
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, m;
int cows[N];
double sum[N];
bool check(double avg)
{
for(int i = 1; i <= n; i++) sum[i] = sum[i - 1] + cows[i] - avg;
double minv = 0;
for(int i = 0, j = m; j <= n; j++, i++)
{
minv = min(minv, sum[i]);
if(sum[j] >= minv) return true;
}
return false;
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> cows[i];
double l = 0, r = 2000;
while(r - l > 1e-5) //保留3位小数 保留k位小数,取eps = -10^-(k+2)
//***这里是r - l,右减左
{
double mid = (l + r) / 2;
if(check(mid)) l = mid; // 这里l r 都可以,把小的干掉就行
else r = mid;
}
printf("%d\n", (int)(r * 1000));
return 0;
}
113. 特殊排序
有N个元素,编号1.2..N,每一对元素之间的大小关系是确定的,关系不具有传递性。
也就是说,元素的大小关系是N个点与N*(N-1)/2条有向边构成的任意有向图。
然而,这是一道交互式试题,这些关系不能一次性得知,你必须通过不超过10000次提问来获取信息,每次提问只能了解某两个元素之间的关系。
现在请你把这N个元素排成一行,使得每个元素都小于右边与它相邻的元素。
你可以通过我们预设的bool函数compare来获得两个元素之间的大小关系。
例如,编号为a和b的两个元素,如果元素a小于元素b,则compare(a,b)返回true,否则返回false。
将N个元素排好序后,把他们的编号以数组的形式输出,如果答案不唯一,则输出任意一个均可。
数据范围
1≤N≤1000
输入样例
[[0, 1, 0], [0, 0, 0], [1, 1, 0]]
输出样例
[3, 1, 2]
注意:不存在两个元素大小相等的情况。
// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.
class Solution {
public:
vector<int> specialSort(int N) {
vector<int> res;
res.push_back(1);
for(int i = 2; i <= N; i++)
{
int l = 0, r = res.size() - 1;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(compare(res[mid], i)) l = mid; // res[mid] < i, 不在左半边里
else r = mid - 1;
}
res.push_back(i);
for(int j = res.size() - 2; j > r; j --) swap(res[j], res[j + 1]);
if(compare(i, res[r])) swap(res[r], res[r + 1]); //i < res[r]
}
return res;
}
};
内容总结
以上是互联网集市为您收集整理的《算法竞赛进阶指南》0.4二分全部内容,希望文章能够帮你解决《算法竞赛进阶指南》0.4二分所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。