Overview

This problem asks for the minimum number of days to make all fields harvestable by optimally assigning \(M\) workers to fields each day. The answer is \(\lceil \sum D_i / M \rceil\) (the total workload divided by the total workforce per day, rounded up).

Analysis

Key Insight: The workforce per day is exactly \(M\)

Since all \(M\) workers must be assigned to some field every day, the total work done per day is exactly \(M\). Over \(T\) days, the total work done is \(T \times M\).

Identifying the Lower Bound

The total work required to harvest all fields is \(\sum_{i=1}^{N} D_i\). Since only \(M\) work can be done per day, at minimum the following number of days is needed:

\[T \geq \left\lceil \frac{\sum D_i}{M} \right\rceil\]

Is This Lower Bound Always Achievable?

Another constraint to consider is that “a single field can progress by at most \(M\) per day,” so the heaviest field requires \(\lceil D_{\max} / M \rceil\) days. However:

\[\lceil D_{\max} / M \rceil \leq \lceil \sum D_i / M \rceil\]

always holds (since \(D_{\max} \leq \sum D_i\)), so ultimately only \(\lceil \sum D_i / M \rceil\) determines the answer.

Verification with Examples

• \(D = [5, 1]\), \(M = 100\): Total \(= 6\), answer \(= \lceil 6/100 \rceil = 1\) day. On day 1, assign 5 workers to field 1, 1 worker to field 2, and the remaining 94 workers somewhere (surplus work has no effect).
• \(D = [3, 3, 3]\), \(M = 2\): Total \(= 9\), answer \(= \lceil 9/2 \rceil = 5\) days. For example, by cleverly distributing 2 workers each day, all fields can have their required work completed in 5 days.

Why the Lower Bound Is Always Achievable

The problem of distributing the required workload to each field over \(T\) days is always feasible if the following conditions are met:

1. Each field \(i\) can receive at most \(M\) work per day → \(D_i \leq T \times M\) (guaranteed when \(T = \lceil \sum D_i / M \rceil\))
2. The total demand of all fields does not exceed total capacity → \(\sum D_i \leq T \times M\) (holds by definition)

Therefore, since \(M\) workers can be freely distributed each day, this lower bound is always achievable.

Algorithm

1. Compute the total sum \(S = \sum_{i=1}^{N} D_i\) of \(D_1, D_2, \ldots, D_N\)
2. Output the answer \(\lceil S / M \rceil = \lfloor (S + M - 1) / M \rfloor\)

Complexity

• Time complexity: \(O(N)\) (just computing the sum of the array)
• Space complexity: \(O(N)\) (storing the input array)

Implementation Notes

• Since \(D_i\) and \(M\) can be up to \(10^9\) and \(N\) up to \(10^6\), the total sum can be around \(10^{15}\). In Python there is no concern about integer overflow, but in C++ and similar languages, long long is required.

• Ceiling division can be correctly computed as (S + M - 1) // M.

• No sorting or binary search is needed; the problem can be solved with a simple sum calculation.

  Source Code

import math

def solve():
    N, M = map(int, input().split())
    D = list(map(int, input().split()))
    
    D.sort(reverse=True)
    
    # Binary search on the number of days
    lo, hi = 1, max(D)
    
    def check(days):
        # With `days` days and M workers per day, total work capacity = days * M
        # Each field i needs D[i] work, but also each field needs at least 1 day
        # (you can do at most D[i] work per day on field i... no, actually you can
        # assign all M workers to one field in one day)
        # 
        # The constraint is: each day, exactly M workers are distributed among fields.
        # A field i needs D[i] total work. In `days` days, each field can get at most
        # `days * M` work (if all workers go there every day), but the real constraint
        # is that the sum of workers assigned each day = M.
        #
        # Key insight: field i needs at least ceil(D[i] / M) days if we could assign
        # all M workers to it. But we need all fields done simultaneously.
        # 
        # Actually, the constraint is:
        # 1) days >= ceil(D_max / M) -- we can't finish the hardest field faster
        #    Wait no, we can assign fewer than M workers per day to a field.
        #    The hardest field needs D_max work. Even if we assign all M workers
        #    every day, it takes ceil(D_max / M) days.
        #    But we also need to handle other fields.
        #
        # With `days` days, total capacity = days * M.
        # We need sum(D) <= days * M (necessary condition).
        # Also, each field needs D[i] work done over `days` days where each day
        # it can receive between 0 and M workers.
        # So each field needs at most M work per day, meaning D[i] <= days * M 
        # for each field (but since days >= 1 and we binary search, this should hold).
        #
        # Actually the only constraint is:
        # - Total work needed: sum(D) <= days * M
        # - No single field requires more than days * M (i.e., D_max <= days * M)
        #   but since M >= 1, if days >= D_max this holds. 
        #
        # Wait, but each field needs D[i] work. We have days days. Each day we 
        # distribute M workers. The question is whether we can distribute M workers
        # across N fields over `days` days such that field i gets at least D[i] total.
        #
        # This is feasible if and only if:
        # 1) sum(D) <= days * M  (enough total capacity)
        # 2) max(D) <= days * M  (no single field needs more than total possible)
        #    But condition 2 is implied by condition 1 when N >= 1... no it's not.
        #    If N=1, both are the same. If N>1, condition 1 is stricter than condition 2
        #    only if sum > max, which is true when N>1 and all D>0.
        #
        # Hmm wait. Actually each day each field can get at most M workers.
        # So field i can get at most days * M over all days. But also, field i
        # can get at most M per day. The real constraint per field is D[i] <= days * M.
        # And the global constraint is sum(D[i]) <= days * M.
        # 
        # Since we can freely distribute M workers each day, as long as 
        # sum(D) <= days * M, we can achieve it. And D_max <= days * M is needed too,
        # but for N >= 1, if sum(D) <= days * M then D_max <= sum(D) <= days * M.
        #
        # So the answer is simply ceil(sum(D) / M).
        # But wait... what about D_max? If D_max > sum/N... no.
        # ceil(sum(D)/M) >= ceil(D_max/M) only if sum >= D_max, which is always true.
        # So the answer is ceil(sum(D) / M).
        
        total = sum(D)
        return days * M >= total
    
    # Actually, we also need days >= ceil(D_max / M)... no wait.
    # If D_max = 10^9, M = 1, N = 1, answer = 10^9 = ceil(10^9 / 1). Correct.
    # The answer is simply ceil(sum(D) / M).
    
    total = sum(D)
    ans = (total + M - 1) // M
    # But also need ans >= ceil(D_max / M) ... which is always <= ceil(sum/M).
    # Hmm, actually not. Consider D = [5, 1], M = 100. sum = 6, ceil(6/100)=1.
    # In 1 day, assign 5 to field 1, 1 to field 2, 94 wasted. Works! Answer = 1.
    print(ans)

solve()

---

This editorial was generated by claude4.6opus-thinking.