题目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#include #include 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)); }}