1.链接:

http://bailian.openjudge.cn/practice/2774/

2.题目:

总Time Limit:
1000ms
Memory Limit:
65536kB
Description
木材厂有一些原木,现在想把这些木头切割成一些长度相同的小段木头,需要得到的小段的数目是给定了。当然,我们希望得到的小段越长越好,你的任务是计算能够得到的小段木头的最大长度。

木头长度的单位是厘米。原木的长度都是正整数,我们要求切割得到的小段木头的长度也要求是正整数。

Input

第一行是两个正整数NK(1 ≤ N ≤ 10000, 1 ≤ K ≤ 10000),N是原木的数目,K是需要得到的小段的数目。
接下来的N行,每行有一个1到10000之间的正整数,表示一根原木的长度。
 

Output
输出能够切割得到的小段的最大长度。如果连1厘米长的小段都切不出来,输出"0"。
Sample Input
3 7
232
124
456
Sample Output
114
Source
NOIP 2004

3.思路:

利用二分查找减少计算的次数

4.代码:

 #include <iostream>
#include <cstdio>
#include <cstring> using namespace std; int main()
{
//freopen("C://input.txt","r",stdin); int i; int n,k;
cin >> n >> k; int sum; //sum of stick length int *arr_len = new int[n];
memset(arr_len , , sizeof(int) * n); sum = ;
for(i = ; i < n; ++i)
{
cin >> arr_len[i];
sum += arr_len[i];
} int max_len = sum / k;
int min_len = ;
int mid_len; int count_k;
int max = ; while(min_len <= max_len)
{
mid_len = (max_len + min_len) / ; count_k = ;
for(i = ; i < n; ++i)
{
count_k += (arr_len[i] / mid_len);
} if(count_k >= k)
{
if(max < mid_len) max = mid_len;
min_len = mid_len + ;
}
else
{
max_len = mid_len - ;
}
} cout << max << endl; delete [] arr_len; return ;
}

最新文章

  1. mysqlroot密码忘记了,修改root密码
  2. C++ do{...}while(0)的好处
  3. C++ 面向对象的三个特点--多态性(二)
  4. 强大的UML建模工具——StarUML
  5. C++中 :: 的意思
  6. STM32片上Flash内存映射、页面大小、寄存器映射
  7. javascript中对数据文本格式化的思考
  8. 2017最新最稳定的合买彩票源码asp+sql2008 新增PK式彩种+全新界面
  9. Unity开发之存档和读档的三种实现方式
  10. hibernate框架学习笔记12:查询优化
  11. ActionScript 3.0 API 中的 Video 类
  12. 解决win环境下访问本机虚拟机中centos7 ftp服务器的问题
  13. Windows编译OpenCV4Android解决undefined reference to std错误
  14. hello2 Source Analisis
  15. FastJSON、Gson和Jackson性能对比
  16. 解决chrome浏览器在win8下没有注册类的问题
  17. WPF 后台重写 DataTemplate
  18. 《Essential C++》读书笔记 之 基于对象编程风格
  19. MVC 在action拦截器中获取当前进入的控制器和aciton名
  20. c# 生成随机N位数字串(每位都不重复)

热门文章

  1. Python之路Day21-自定义分页和cookie
  2. BSBuDeJie_04
  3. springmvc数组参数传递
  4. 段错误bug的调试
  5. 使Asp.net Core同时支持输出Json/Xml
  6. UITableViewBase&amp;nbsp;UI_09
  7. unix命令自我总结
  8. JS 数组、对象的深拷贝
  9. 邮件服务器安装--Postfix + Dovecot + Squirrelmail--CentOS 6.4
  10. Tomcat证书安装(pfx和jks)
  11. python 精确计算与向上取整 decimal math.ceil
  12. mysql存储过程实例,查询多参数赋值
  13. babel-polyfill的引用和使用
  14. NoHttp封装--05 文件下载
  15. JAVA消息服务JMS规范及原理详解
  16. 词频统计 SPEC 20160911
  17. Django组件(三) Django之中间件
  18. Spring依赖注入:基于xml配置
  19. 用字典给Model赋值并支持map键值替换
  20. Google TensorFlow 学习笔记一 —— TensorFlow简介