[木桶差异] 炸鸡排

炸鸡排

题目描述

小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已经全部熟了，无法继续进行

解题分析

给了n个鸡排，k口锅，并且k口锅上始终要有鸡排被煎着，如何才能使鸡排被煎的时间最长呢？

观察例子:

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

其实很好理解，如果说煎鸡排需要的总时间除以炸锅的数量得到的平均一口锅上煎鸡排的时间大于每个鸡排需要煎的时间，那我们就可以轮番在锅上随时拿下拿上鸡排，这样我们就可以达到最长的煎鸡排的时间，也就是全部时间加起来除以锅的数量得到的平均时间，3/2=1.5。

那要是出现了那些煎的时间比较长，以至于它的时间超过平均时间的鸡排呢？那肯定会出现鸡排没煎完的情况（因为必须保证k口锅都要有鸡排），所以，我们可以发现，这种鸡排完全不影响我们能煎鸡排的最长时间的计算，单独给它一口锅就行了嘛。

然后再算剩下鸡排在剩下锅能煎的平均时间就是最长时间了。

代码实现

#include <iostream>
using namespace std;

int t[10001];
bool ty[10001];
int s=0;

int main(){
    int n,m; cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>t[i];
        s+=t[i];
    }
    int p=m;
    bool ye=false;
    while(ye==false){
        ye=true;
        int tempp=p;
        for(int i=1;i<=n;i++){
            if(t[i]>s*1.0/tempp && !ty[i]){
                s-=t[i];
                ty[i]=true;
                p--;
                ye=false;
            }
        }
    }
    printf("%.3lf\n",s*1.0/p);
    return 0;
}