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

# 洛谷 P4343 [SHOI2015]自动刷题机

3周前 (08-31) 25次浏览

## 思路

• 如果 (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;

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() {
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;
}
``````