浙江网站建设推荐,怎么制作网页教程,个人怎么开通微信小程序,wordpress主题怎么修改102. 最佳牛围栏 农夫约翰的农场由N块田地组成#xff0c;每块地里都有一定数量的牛,其数量不会少于1头#xff0c;也不会超过2000头。 约翰希望用围栏将一部分连续的田地围起来#xff0c;并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。 围起区域内至少需要包…102. 最佳牛围栏 农夫约翰的农场由N块田地组成每块地里都有一定数量的牛,其数量不会少于1头也不会超过2000头。 约翰希望用围栏将一部分连续的田地围起来并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。 围起区域内至少需要包含 F块地其中 F会在输入中给出。 在给定条件下计算围起区域内每块地包含的牛的数量的平均值可能的最大值是多少。 输入格式 第一行输入整数 N和 F数据间用空格隔开。 接下来 N行每行输出一个整数第i1行输出的整数代表第i片区域内包含的牛的数目。 输出格式 输出一个整数表示围起区域内每块地包含的牛的数量的平均值可能的最大值乘以1000得到的数值。 数据范围 1≤N≤100000 1≤F≤N 输入样例 10 6 6 4 2 10 3 8 5 9 4 1 输出样例 6500 #include iostream
#include algorithmusing 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^-(k2) //***这里是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,则comparea,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:vectorint specialSort(int N) {vectorint 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;}
}; 转载于:https://www.cnblogs.com/wmxnlfd/p/10847657.html
