E - 在家无聊不(武汉加油) POJ - 3273 (简单二分答案)

文章目录[x]
  1. 1:原题链接
  2. 2:题意
  3. 3:思路
  4. 4:参考代码


原题链接

http://poj.org/problem?id=3273

题意

给你的值,代表天,让你将这天恰好分成段连续和,让这段和里面的最大值最小。

思路

因为这个和具有单调性,二分答案,即二分最大连续和,下界取天的最大值,上界取天的和,从而找到最优值。

参考代码

#include <algorithm>
#include <cmath>
#include <cstdio>

using namespace std;
int n, m, a[100005];
bool check(int mid) {
  int sum = 0, num = 1; //查询每组上限为mid的情况下的组数
  for (int i = 1; i <= n; i++) {
    if (sum + a[i] <= mid) {
      sum += a[i];
    } else {
      sum = a[i];
      num++;
    }
  }
  return num > m; //组数偏大,说明mid偏小
}
int main() {
  scanf("%d%d", &n, &m);
  int maxn = -1, sum = 0;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    maxn = max(maxn, a[i]);
    sum += a[i];
  }
  int l = maxn, r = sum;
  int mid = (l + r) / 2;
  while (l < r) {
    if (check(mid)) {
      l = mid + 1;
    } else {
      r = mid - 1;
    }
    mid = (l + r) / 2;
  }
  printf("%d\n", mid);
  return 0;
}


点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像