洛谷 P4343 [SHOI2015]自動刷題機

• 2020 年 8 月 31 日
• 筆記
• 二分答案, 基礎算法——二分

思路

二分答案

顯然的二分答案，但是因為二分判定條件 \(\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 << "-1\n", 0;
  cout << minn << " " << maxn << '\n';
  return 0;
}