题目:

这题有点坑,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 ;
}

最新文章

  1. ng-if ng-show ng-hide 的区别
  2. Win10 无法完全关机问题
  3. C# 线程系列三 定时器线程
  4. IOS照片框架
  5. INNO 补丁制作技术, 打开 INNO 补丁制作方法的第一页
  6. Java for LeetCode 030 Substring with Concatenation of All Words【HARD】
  7. 词典对象 NSDictionary与NSMutableDictionary
  8. AngularJs学习笔记--concepts(概念)
  9. iOS-自定义导航栏后侧滑返回功能失效
  10. oracle 常用SQL语法手册
  11. Mybatis学习——一对多关联表查询
  12. filter过滤器的使用
  13. Python数据分析Python库介绍(1)
  14. 2.4. 属性(Core Data 应用程序实践指南)
  15. 读书笔记 effective c++ Item 13 用对象来管理资源
  16. 从零开始搭建口袋妖怪管理系统(2)-借助ngRoute实现详情页面跳转
  17. C语言关闭日志文件时忘了将日志文件全局变量指针置为NULL
  18. 【Git】Git使用记录: 基于git ignore文件将remote上的文件untrack
  19. Vue + Element UI 实现权限管理系统 前端篇(十二):用户管理模块
  20. 进程描述和控制(os 笔记二)

热门文章

  1. ubuntu DNS 出错,用以下命令可以解决
  2. 解决:[WARNING] fpm_children_bury(), line 215: child 2736 (pool default) exited on signal 15 SIGTERM after 59.588363 seconds from start
  3. 关于TCP的三次握手和四次分手 专题
  4. Linq、延迟加载、直接加载
  5. 硅谷最有名的帮派:如果你不知道PayPal黑帮
  6. ZBrush通过绘制层得到子物体
  7. 浅谈冒烟测试(Smoke Testing)
  8. js-数组和字符串转化
  9. CSS3特效——六面体
  10. android studio2.2 配置NDK