Minimize maximum

Very interesting topic

Title Description

Include a n The sequence of positive integers is divided into m Consecutive subsequences （ Each positive integer happens to belong to a sequence ）. Set the first i The sum of the numbers of the sequences is S(i), Your task is to make all S(i) The maximum value of is as small as possible .

For example, the sequence 1 2 3 2 5 4 Divide into 3 The optimal scheme of the sequences is 1 2 3 | 2 5 | 4, among S(1)、S(2)、S(3) Respectively 6、7、4, The maximum is 7;

If you divide it into 1 2 | 3 2 | 5 4, Then the maximum value is 9, It's not as good as just now .n<=10^6, The sum of all numbers does not exceed 10 ^ 9.

Ideas

“ The maximum value shall be as small as possible ” Is a very common optimization goal . Let's consider a new problem ： Can the input sequence be divided into m Consecutive subsequences , Make all S(i) Not more than x? Let's use the predicate to answer this question P(x) Express , Then let P(x) True minimum x Is the answer to the original question .

that x How to get the value ？

My idea is to increase from childhood , Find the right , The smallest one is the sum of the array divided by the number of subsequences divided . for example 1 2 3 2 5 4, that x Just from 6 Start .

Code

numbers=[1,2,3,2,5,4,4]
m=int(input())
nums=sum(numbers)
if nums%m!=0:
    a=nums//m+1
else:
    a=nums//m
while True:
    b=0
    for i in range(m-1):
        n=0
        d=b
        for i in range(d,len(numbers)):
            temp=sum(numbers[b:i+1])
            if temp>a:
                b=i
                break
            elif temp==a:
                b=i+1
                break
    if sum(numbers[b:])<=a:
        print(a)
        break
    else:
        a+=1

If you have any shortcomings, please leave a message in the comment area ~~~