学步园

题目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 = 0;
        scanf("%d%d",&m,&n);
        for(int i=1; i<=m; i++)
            scanf("%d",&a[i]) , tot += a[i];
        int low = 1 , high = tot , mid;
        while(low <= high)
        {
            mid = (low + high) >> 1;
            int i = 1 , k , count = 0 , ok = 1;
            while(i<=m)
            {
                if(a[i] > mid)
                { ok = 0; break;}
                int sum = 0;
                for(k=i; k<=m; k++)
                {
                    sum += a[k];
                    if(sum > mid) break;
                }
                i = k;
                count++;
            }
            if(!ok || count > n) low = mid + 1;
            else if(count == n)     high = mid - 1;
            else                    high = mid - 1;
        }
        printf("%d\n",max(low,high));
    }
}