题目1502：最大值最小化（二分答案）
九度OJ
Java
import java.util.Scanner;
public class Main {
public static int max(int x ,int y){
return x > y ? x : y;
}
public static int solve(int tot , int m , int n ,int a[]){
int low = 1 , high = tot;
while(low <= high){
int mid = (low + high) / 2;
int i = 1 , count = 0 , k , flag = 1 ;
while(i <= m){
if(a[i] > mid){
flag = 0; break;
}
int sum = 0;
for(k = i; k <= m; k++){
sum += a[k];
if(sum > mid) break;
}
i = k;
count++;
}
if(flag == 0 || count > n) low = mid + 1;
else if(count == n) high = mid - 1;
else high = mid - 1;
/*
if(count <= n) high = mid - 1;
else low = mid + 1;
*/
}
return max(low , high);
}
public static void main(String[] args){
final int N = 510 , M = 510;
int cas,n,m,tot;
int[] a = new int[M];
Scanner cin = new Scanner(System.in);
cas = cin.nextInt();
while((cas--) != 0){
m = cin.nextInt();
n = cin.nextInt();
tot = 0;
for(int i = 1; i <= m; i++){
a[i] = cin.nextInt();
tot += a[i];
}
int res = solve(tot,m,n,a);
System.out.println(res);
}
}
}
C++
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 510
#define M 510 int a[M],tot; int main()
{
int cas,n,m;
scanf("%d",&cas);
while(cas--)
{
tot = ;
scanf("%d%d",&m,&n);
for(int i=; i<=m; i++)
scanf("%d",&a[i]) , tot += a[i];
int low = , high = tot , mid;
while(low <= high)
{
mid = (low + high) >> ;
int i = , k , count = , ok = ;
while(i<=m)
{
if(a[i] > mid)
{ ok = ; break;}
int sum = ;
for(k=i; k<=m; k++)
{
sum += a[k];
if(sum > mid) break;
}
i = k;
count++;
}
if(!ok || count > n) low = mid + ;
else if(count == n) high = mid - ;
else high = mid - ;
}
printf("%d\n",max(low,high));
}
}