cdoj 1255 斓少摘蘋果 貪心

斓少摘蘋果

Time Limit: 20 Sec

Memory Limit: 256 MB

題目連接配接

http://acm.uestc.edu.cn/#/problem/show/1255

Description

斓少家的院子裡有N棵蘋果樹，每到秋天樹上就會結出Fi個蘋果。

蘋果成熟的時候，斓少就會跑去摘蘋果。

斓少摘蘋果的方式非常的奇特，每次最多可以選擇M個蘋果并摘下來。

但是摘下來的蘋果兩兩一定不是來自同一棵樹，問斓少最少摘多少次，才能使得每個蘋果都被摘下來呢？

Input

第一行輸入一個數N和M（1≤M≤N≤106），代表蘋果樹的數量，和斓少每次最多摘多少個。

第二行輸入N個數，第i個數Fi（0≤Fi≤106）代表這一棵樹上一共有多少個蘋果

Output

輸出一個數字，表示最少選擇次數

Sample Input

5 3
3 2 3 2 4      

Sample Output

5      

HINT

題意

題解：

題解：

假設斓少每次都能取到m個蘋果(不足m個時全取到)，那麼這個次數顯然為Ti = (sigma(Fi)-1)/m + 1

由于對于每一天，每次都隻能最多選這一棵樹的一個果子，那麼至少要取max（Fi）次

現在，令Gi = max(max(Fi),Ti)

現在證明是可以在Gi次取完的

我們現在把模型轉換成把N個寬度為1，長度分别的Gi，顔色為i的矩形。

每個矩形拆分成Gi個1*1的矩形，填充至一個m*Gi的矩形内（可以不填滿），滿足在Gi行中，每一行都沒有同樣的顔色矩形

我們從第一列，第一種顔色開始填充，每當這一列填滿(即高度到達Gi)時填充下一列，如果該顔色用完就換下一種顔色。

現在證明，這樣可以保證每行都不會有同一種顔色。

對于每一種顔色i，由于Gi>=max(Fi)>=Fi，那麼任意一種顔色最多在相鄰的兩列中出現。

如果隻在一列中出現，顯然都在不同一行。

如果在相鄰的兩列，那麼一列填充到了頂部，下列從最底部開始。設一列填充了ai個，下列填充了bi個，顯然當且僅當ai+bi>Gi時才會出現在同一行的情況，但又有ai+bi=Fi<=max(Fi)<=Gi,是以也不會在同一行出現。

于是我們證明，斓少可以在Gi次選完所有的果子。

是以答案為 max( Ti , max(Fi) )，時間複雜度為O(N)

代碼：

#include <cstdio>
#include <algorithm>

long long sum;
int mx;

int main()
{
    int N, M;
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; ++i)
    {
        int f;
        scanf("%d", &f);
        sum += f;
        mx = std::max(mx, f);
    }
    printf("%lld\n", std::max((sum + M - 1) / M, 1ll * mx));
    return 0;
}