28701: 炸鸡排

greedy, http://cs101.openjudge.cn/practice/28701/

小P买了n块鸡排，想将它们做成美味的炸鸡排，其中第i块鸡排需要t[i]秒炸熟。小P只有一个炸锅，炸锅内可以放置k(k≤n)块鸡排。小P是个完美主义者，他要求任意时刻炸锅内必须恰有k块鸡排。他可以在任意时刻改变锅内正在炸的鸡排，只需保证已经熟了的鸡排不能继续留在锅中。小P希望知道炸鸡排最多可以持续多少时间。

例如，小P的三块鸡排需要分别需要1,1,1的时间炸熟，炸锅内需要放置2块鸡排，那么他决定在第一个0.5秒炸1和2两块鸡排，第二个0.5秒炸2和3两块鸡排，第三个0.5秒炸1和3两块鸡排，共持续了1.5秒。

输入

第一行输入两个正整数n和k，k≤n 第二行输入n个正整数，代表n块鸡排分别需要炸熟的时间t[1],t[2]...t[n] 输入数据保证，n≤1000，0＜t[i]≤1000000

输出

输出一个双精度浮点数，代表炸鸡排最多可以持续的时间，结果保留三位小数。

样例输入

4 2
5 1 1 2

样例输出

4.000

# 第1秒，放置1和2
第2秒，放置1和3
第3、4秒，放置1和4
至此，2，3，4已经全部熟了，无法继续进行

提示

Greedy

来源

2024 TA-xjk

思路：最理想情况是每块鸡排都炸完,用时为所有鸡排用时的平均值如果耗时最长的鸡排比其他鸡排的平均用时更长,说明无论其他鸡排怎么摆都会使那块鸡排炸不完, 那索性那块鸡排就一直放那炸,考虑剩下的鸡排否则就可以达到最理想情况:平均用时

python

# 24n2400011339 官祺云 物院
n, k = map(int, input().split())
t = list(map(int, input().split()))
t.sort()
s = sum(t)
while True:
    if t[-1] > s / k:
        s -= t.pop()
        k -= 1
    else:
        print(f'{s / k:.3f}')
        break

python

import sys

def main():
    input = sys.stdin.read
    data = input().split()
    
    n = int(data[0])
    k = int(data[1])
    times = [int(data[2 + i]) for i in range(n)]
    
    # 计算总炸制时间
    total_time = sum(times)
    
    # 对炸制时间进行排序
    times.sort()
    
    # 初始最大持续时间为总炸制时间除以 k
    max_time = total_time / k
    
    # 如果最长的炸制时间大于或等于 max_time，则需要调整 k 的值
    if times[-1] > max_time:
        for i in range(n - 1, -1, -1):
            if times[i] <= max_time:
                break
            total_time -= times[i]
            k -= 1
            max_time = total_time / k
    
    # 输出结果，保留三位小数
    print(f"{max_time:.3f}")

if __name__ == "__main__":
    main()

思路：

很容易看出当各个时间 $t_{i}$ 差距不太大时，所有鸡排都能被炸完，此时最长用时一定为

T_{0} = \frac{\sum_{i = 1}^{n} t_{i}}{k}

那么什么时候差距“太大”呢？根据示例的启发我们可以想到，假设有 $m$ 块鸡排一直在炸，剩下 $n - m$ 块差距不太大的鸡排，可以用最佳方法炸完，其用时为

T_{m} = \frac{\sum_{i = m + 1}^{n} t_{i}}{k - m}

此时若剩下的 $m$ 块鸡排均未被炸完，则它们就是“时间充分大的”，由于并没有比一直炸更好的处理方式，所以此时的时间就是最优的。显然，有 $m < k$ ,于是可以从 $k - 1$ 开始枚举。这就是本题思路。

python

# 尹显齐25物院
[n,k] = map(int,input().split())
nums = sorted(list(map(int,input().split())),reverse = True)
yes = 1
for i in range(k-1,0,-1):
    if nums[i-1] > sum(nums[i:])/(k-i):
        time = sum(nums[i:])/(k-i)
        yes = 0
        break
if yes:
    time = sum(nums)/k
print(f"{time:.3f}")

28701: 炸鸡排 ​

28701: 炸鸡排