POJ 1064 Cable master (二分答案,G++不过,C++就过了)
2024-08-31 10:55:05
题目:
这题有点坑,G++过不了,C++能过。
条件:n个数据a[],分成k段,结果精度要求两位小数。
问题:每段最长为多少?
思路:因为精度要求为两位小数,我先把所有的长度a[]*100。
我们对答案二分搜索,把l设置为0,r设置为1000*10000*100+1(数据量*每个数据最大的大小*精度+1)。
这样我们搜索的数就不用处理精度了,我们可以二分算出结果然后除以100。
代码:
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <set>
#include <math.h>
#include <queue>
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
typedef long long ll;
#define INF 2147483647 //输入
int n, k;
double a[]; //返回分成k段最大的段长
double solve(ll sum) {
ll l = , r = sum+; //二分的左右端
ll mx = ; //保存结果 while (l < r) {
ll mid = (l + r) / ;
ll sum = ; //段数求和
for (int i = ; i < n; i++) sum += a[i] / mid; //每段长mid,可以分成k段
if (sum >= k) {
mx = max(mx, mid); //更新答案
l = mid + ;
}
else {
r = mid;
}
}
return 1.0*mx/;
} int main() {
cin >> n >> k;
ll sum = ;
for (int i = ; i < n; i++) {
cin >> a[i];
a[i] *= ; //将段长乘以100
sum += a[i]; //对段长求和
} printf("%.2lf",solve(sum)); getchar(); getchar();
return ;
}
最新文章
- ng-if ng-show ng-hide 的区别
- Win10 无法完全关机问题
- C# 线程系列三 定时器线程
- IOS照片框架
- INNO 补丁制作技术, 打开 INNO 补丁制作方法的第一页
- Java for LeetCode 030 Substring with Concatenation of All Words【HARD】
- 词典对象 NSDictionary与NSMutableDictionary
- AngularJs学习笔记--concepts(概念)
- iOS-自定义导航栏后侧滑返回功能失效
- oracle 常用SQL语法手册
- Mybatis学习——一对多关联表查询
- filter过滤器的使用
- Python数据分析Python库介绍(1)
- 2.4. 属性(Core Data 应用程序实践指南)
- 读书笔记 effective c++ Item 13 用对象来管理资源
- 从零开始搭建口袋妖怪管理系统(2)-借助ngRoute实现详情页面跳转
- C语言关闭日志文件时忘了将日志文件全局变量指针置为NULL
- 【Git】Git使用记录: 基于git ignore文件将remote上的文件untrack
- Vue + Element UI 实现权限管理系统 前端篇(十二):用户管理模块
- 进程描述和控制(os 笔记二)
热门文章
- ubuntu DNS 出错,用以下命令可以解决
- 解决:[WARNING] fpm_children_bury(), line 215: child 2736 (pool default) exited on signal 15 SIGTERM after 59.588363 seconds from start
- 关于TCP的三次握手和四次分手 专题
- Linq、延迟加载、直接加载
- 硅谷最有名的帮派:如果你不知道PayPal黑帮
- ZBrush通过绘制层得到子物体
- 浅谈冒烟测试(Smoke Testing)
- js-数组和字符串转化
- CSS3特效——六面体
- android studio2.2 配置NDK