Codility MinMaxDivision

最近发现了一个刷题网站：https://app.codility.com/programmers/lessons

这个网站做题目时候的界面让我惊艳到了

首先这是题目界面：

然后点击start, 出来的是这样一个界面

有计时功能，还有自己编写测试样例功能，还有很多其他功能。给人营造一种完全融入到刷题状态的感觉。

点击提交之后的结果如下：

还可以分析你程序的时间效率。满分是100%

从体验来说，比LeetCode 强很多了。但是他的题目好像很少。

接下来说这道题目。从一个数组中划分k个块，要求k个块中最大数组和最小，我一开始想用动态规划，结果发现，数据范围太大，不是动态规划的范畴。

一看题目的类别是二分。根据之前刷题的经验，求最大中的最小，或者最小中的最大，要么是二分，要么是动态规划。

二分的话，得找到用来二分的对象。这道题目应该对结果进行二分。就是k个块中最大数组和的最小值。

从0 到 sum 进行二分，那么二分中的判断条件就是该数组是否可以划分小于等于k个块，并且每个块的和都小于等于mid

如果符合条件，说明mid的值是过大的，还可以再小一点，end=mid-1;

如果不符合条件，说明mid的值是过小的，start=mid+1;

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <vector>

int n,m,k;
using namespace std;

bool isTrue(vector<int> &A,int sum,int k)
{
    int s=0;
    int p=0;
    for(int i=0;i<A.size();i++)
    {
        if(s>sum)
        {
            p++;
            i--;
            s=0;
        }
        s+=A[i];
    }
    
    if(s<=sum)
        p++;
    else
        p+=2;
    
    if(p<=k)
        return true;
    return false;
}

int solution(int K, int M, vector<int> &A) {
    
    int end=0;
    int start = 0;
    for(int i=0;i<A.size();i++)
    {
        end += A[i];
        start = max(start,A[i]);
    }
    
    while(start<end)
    {
        int mid = (start+end)/2;
        if(isTrue(A,mid,K))
        {
             end=mid;
            
        }
        else
        {
            start=mid+1;
        }
    }
    
    return start;
    
    // write your code in C++14 (g++ 6.2.0)
}

Codility MinMaxDivision

原文：https://www.cnblogs.com/dacc123/p/11459449.html