Codility MinMaxDivision
这个网站做题目时候的界面让我惊艳到了
首先这是题目界面：
然后点击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)
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-09-04 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读