当前位置:网站首页>烘干衣服问题
烘干衣服问题
2022-08-10 23:15:00 【chengqiuming】
一 问题描述
二 算法设计
可以用二分法来求最少用的时间,关键地方是用 mid 来缩小范围。判断函数是这个问题的关键。
简单情况:如果所有的 a[i] 都小于 mid,那么肯定是可行的,都不需要用烘干机,自然风干也不会超过 mid。
如果有的 a[i] 大于 mid,怎样处理呢?
可以让所有 a[i] 大于 mid 的衣服使用烘干机,而 a[i] 不大于 mid 的衣服自然风干就可以了。
假设衣服 a[i] > mid,用了 t 时间的烘干机,剩余的时间 mid-t 选择自然风干。那么 a[i] = k*t + mid-t,t = (a[i]-mid)/(k-1)。
只需要看这些 a[i]>mid 的衣服用的烘干时间的总和有没有超过 mid,如果超过了,肯定是不满足的。
三 代码
package com.platform.modules.alg.alglib.poj3104;
import java.util.Arrays;
public class Poj3104 {
private int n;
private int k;
private Integer a[] = new Integer[100005];
private String output = "";
public Poj3104() {
for (int i = 0; i < a.length; i++) {
a[i] = 0xFFFFF;
}
}
boolean judge(int x) {
int sum = 0;
for (int i = 0; i < n; i++) {
if (a[i] > x)
sum += (a[i] - x + k - 2) / (k - 1); // 上取整
if (sum > x)
return false;
}
return true;
}
void solve() {
Integer l = 1, r = a[n - 1], ans = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (judge(mid)) {
ans = mid;
r = mid - 1; // 减小
} else
l = mid + 1; // 增大
}
output += ans.toString();
output += "\n";
}
public String cal(String input) {
String[] line = input.split("\n");
n = Integer.parseInt(line[0]);
String[] words = line[1].split(" ");
for (int i = 0; i < n; i++) {
a[i] = Integer.parseInt(words[i]);
}
Arrays.sort(a, 0, n - 1);
k = Integer.parseInt(line[2]);
if (k == 1) {
output += a[n - 1].toString();
output += "\n";
}
solve();
return output;
}
}
四 测试
边栏推荐
猜你喜欢
随机推荐
VMware 虚拟机开启Ip地址自动更换解决
【MySQL】mysql因为字符集导致left join出现Using join buffer (Block Nested Loop)
房间虚拟样板间vr制作及价格
【Linux】宝塔面板设置MySQL慢查询日志,未走索引日志
MySQL之JDBC编程增删改查
Kotlin 由浅入深,带你搞懂协程异常处理的那点事
如何反弹shell
MySQL之JDBC编程增删改查
高性能MySQL核心整理强势来袭
虎牙自动发弹幕换牌子
PlaidCTF 2022 Amongst Ourselves:Shipmate writeup
一、ICESat-2数据查询,下载,与处理
leetcode:357. 统计各位数字都不同的数字个数
线程相关知识点
XSLeaks 侧信道攻击 (unfinished)
leetcode:355. 设计推特
Kubernetes 计算CPU 使用率
App 启动速度优化系列:如何用一个placeholderUI来做初始化工作
信息系统项目管理师核心考点(六十五)信息安全基础知识网络安全
PlaidCTF 2022 Amongst Ourselves: Shipmate writeup