• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

洛谷 P4343 [SHOI2015]自动刷题机

开发技术 开发技术 3周前 (08-31) 25次浏览

思路

二分答案

显然的二分答案,但是因为二分判定条件 (text{wa}) 了好几遍……

可以发现,(n) 越大,(k) 就越小,所以答案是有单调性的,因此可以用两个二分,一次求最大值,一次求最小值,这里以求最大为例。

判定一个答案是否可行可以线性扫一遍直接求,在判定中记录过的题数 (cnt),由于 (n) 越大,(k) 就越小,所以:

  • 如果 (cnt=k),更新最大值 (maxn=mid),并令 (l=mid+1),继续查找更大的值
  • 如果 (cnt<k),说明 (mid) 右边的值都不可行,那么就将 (r) 左移,设为 (r=mid-1)
  • 如果 (cnt>k),说明 (mid) 左边的值都不可行,那么就将 (l) 右移,设为 (l=mid+1)

这样最后找的的值就是最大值了,最小值同理。

注意:

  1. 记得开 (text{long long}),否则会 (text{wa})
  2. 右端点要设置得足够大
  3. 在求出最大值之后可以直接将其作为求最小值时的二分右端点

代码

/*
  Name: P4343 [SHOI2015]自动刷题机
  Author: Loceaner
  Date: 31/08/20 17:58
  Description:
  Debug: 二分判定条件出错 
*/
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;

const int A = 1e5 + 11;
const int B = 1e6 + 11;
const int mod = 1e9 + 7;
const int inf = 1e18;

inline int read() {
  char c = getchar();
  int x = 0, f = 1;
  for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
  for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return x * f;
}

int n, k, a[A], maxn = -inf, minn = inf, cnt, now;

inline bool check(int x) {
  cnt = 0, now = 0;
  for (int i = 1; i <= n; i++) {
    now += a[i];
    if (now < 0) now = 0;
    if (now >= x) cnt++, now = 0;
  }
  return cnt == k;
}

signed main() {
  n = read(), k = read();
  for (int i = 1; i <= n; i++) a[i] = read();
  int l = 0, r = inf;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (check(mid)) maxn = mid, l = mid + 1;
    else if (cnt < k) r = mid - 1;
    else if (cnt > k) l = mid + 1;
  }
  l = 1, r = maxn;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (check(mid)) minn = mid, r = mid - 1;
    else if (cnt > k) l = mid + 1;
    else if (cnt < k) r = mid - 1;
  }
  if (minn == inf || maxn == -inf) return cout << "-1n", 0;
  cout << minn << " " << maxn << 'n';
  return 0;
}

喜欢 (0)