【ZOJ 3778】【C++心路历程40】【コック】【欲張り】【構想題】

はははははもともと1本の试験问题で、発见された后にどんなに面白いと感じます~【问题の说明】
中秋の佳節、xxx家の親戚や友人が一堂に会した.アルバイトのコックとして、xxxはみんなのためにn料理を作る必要があります.i番目の料理にはxiの工程があることが知られており、xxxは毎分mの料理を同時に作ることができる工程である.今xxxにnから料理までの最短時間を計算してください.
【入力形式】
入力された第1の動作整数nとmは、タイトルの説明のような意味を持つ.2行目にはn個の整数があり、i番目の整数はxiであり、i番目の料理の工程数を表す.
【出力形式】
n料理が完成する最短時間を表す整数を出力します.
【入力サンプル】
【例1】3 2 2 2 2
【サンプル1】10 6 1 2 3 4 5 6 8 10
【出力サンプル】
【様式1】3
【例2】10
【様式解釈】
【サンプル1の説明】1分目に第1の第2〜料理の第1の工程を同時に完了すると、3つの料理の残りの工程はそれぞれ1 1〜2となる.2分目に第1の料理の第2の工程を完了し、同時に第3の料理の第1の工程を完了すると、3の料理の残りの工程はそれぞれ0 1である.3分目に2番目の料理と3番目の料理の2番目の工程が完了すると、3番目の料理の残りの工程はそれぞれ0 0 0になります.【データ範囲】1<=n,m<=40000 1<=xi<=40000.この問題の比較的明らかな構想は大きいから小さいまで並べ替えて、しかし並べ替えた後に何をするべきです><難しくなくて発見して、最大の時間のあの料理と答えは密接に関連しています.例えばm>=nの場合、総時間は明らかに最大の料理を作る時間である.では、小さいですか.最適化を考慮するとansはsum/mという値より小さくはない.最大のディスク時間をMaxに設定します.
Maxが小さい場合(csdnが小さい場合は打てません???sum/mなので、すべての料理の時間はsum/mより小さいです.ではsum/mの時間内に必ずすべての料理を完成させることができます(欲張り思想).
Max>=sum/mの場合、答えはMaxです.簡単な証明は以下の通りです:sum/mがMaxより小さいためsumがMax*mより小さい(sum-Max)/(m-1)がMax(*)より小さい式は何を説明しますか?毎回作るたびにMaxを持って作る以外に、残りの料理は1分間に(m-1)個の料理を作ることができ、この(m-1)個の料理は必ずMaxの時間内に完成できるというサブ問題に分けられていることを説明した.だから総時間はMaxを超えません.実際、自分で証明するときは実は(*)式を考えてから、彼の正しさを押しました.http://blog.csdn.net/xiaoming_pこの結論はサブ問題に分類できるからだ.
しかし、Maxがsum/mより小さい場合の証明については、確かに良い方法は思いつかないので、しばらくここに置いておきましょう.でも、感じられる、この条件を満たした、きっと正しい...それが欲張りの魅力なのかもしれない.

#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn=40005;
const int maxm=10005;
int n,m,a[maxn],sum=0,mx=0;
void init()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        sum+=a[i];mx=max(mx,a[i]);
    }
    if(m>=n) printf("%d",mx);
    else
    {
        int tt=sum/m;
        if(tt>mx)
        {
            if(sum%m) tt++;
            printf("%d",tt);
        }
        else
            printf("%d",mx);
    }
}

int main()
{
//  freopen("in.txt","r",stdin);
    init();


    return 0;
}