当前位置:网站首页>【集训DAY3】挖金矿【二分答案】
【集训DAY3】挖金矿【二分答案】
2022-08-09 22:35:00 【VL——MOESR】
思路:
直接二分平均值,然后把数组全部减去平均值,贪心求每一列的最大值,然后判断是否合法就行了
c o d e code code
#include<iostream>
#include<cstdio>
using namespace std;
int n, m, tot;
double a[100010];
bool check(double x) {
double s1 = 0, s2 = 0, s3 = 0;
tot = 0;
for(int i = 1; i <= n; i ++) {
s1 = s2 = a[++ tot] - x;
for(int j = 2; j <= m; j ++)
s1 = s1 + a[++ tot] - x, s2 = max(s1, s2);
s3 += s2;
}
return s3 >= 0;
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
tot ++, scanf("%lf", &a[tot]);
double l = 0, r = 1000000000.0, ans = 0;
while(l + 0.000001 < r) {
double mid = (l + r) / 2;
if(check(mid)) l = mid, ans = max(ans, mid);
else r = mid;
}
printf("%.4lf", ans);
return 0;
}
边栏推荐
猜你喜欢
32 JZOF 】 【 print down on binary tree
IT传奇人物菲尔德的转型经验教训及给CIO的建议
金仓数据库 KingbaseGIS 使用手册(6.4. 几何对象存取函数)
了解什么是架构基本概念和架构本质
[Interface Test] Decoding the request body string of the requests library
The latest "Grain Academy Development Tutorial" in 2022: 10 - Front-end payment module
全球不用交税的国家,为什么不交
Qt 之 QDateEdit 和 QTimeEdit
ABAP中Collect的用法
MVC与MVVM模式的区别
随机推荐
技术盛宴!华云数据携六大议题亮相OpenInfra Days China
Filament-Material 绘制基本图形
用函数统计最长单词的字母数量
后台管理实现导入导出
【Burning】It's time to show your true strength!Understand the technical highlights of the 2022 Huawei Developer Competition in one article
Force Buckle: 474. Ones and zeros
高手这样看现货白银走势图
CAD 截断线段
直播平台怎么搭建,原生js实现编辑器撤消/恢复功能
打包报错 AAPT: error: failed to read PNG signature: file does not start with PNG signature.
直播预告 | ICML 2022 11位一作学者在线分享神经网络,图学习等前沿研究
Cmake 用法记录
2021年国内外五大BI厂商——优秀的商业智能工具推荐
SRv6 performance measurement
k8s部署mysql
Mysql/stonedb - slow SQL - 2022-08-09 Q16 analysis
Qt 之 QDateEdit 和 QTimeEdit
JS--popstate事件--使用/教程/实例
【哲理】事教人
leetcode 20. Valid Parentheses 有效的括号(中等)