[COGS 2642][BZOJ 4590][Shoi 2015]自动刷题机
book
归档:
OI
flag
题目描述
思路
合法的n是一个区间,可以分成两次求,二分n的范围。注意有一些关于long long和代码的细节,这个checker还是很好写的
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxl = 100010;
ll mlog[maxl];
int lll, k;
int ck(ll nn)
{
ll ans = 0, line = 0;
for (int i = 1; i <= lll; ++i)
{
line += mlog[i];
if (line < 0) line = 0;
if (line >= nn) ++ans, line = 0;
}
if (ans > k) return 1;
if (ans == k) return 0;
if (ans < k) return -1;
}
int main()
{
freopen("autoac.in", "r", stdin);
freopen("autoac.out", "w", stdout);
cin >> lll >> k;
ll rmax = 0, rsum = 0;
for (int i = 1; i <= lll; ++i)
cin >> mlog[i], rsum += (mlog[i] > 0 ? mlog[i] : 0), rmax = max(rmax, rsum);
rmax++;
//================================
ll maxn = 0, minn = 0;
ll l = 1, r = rmax, mid;
while (l + 1 != r)
{
mid = (l + r) >> 1;
int st = ck(mid);
if(st == 1)
l = mid;
else r = mid;
}
if (ck(l) == 0) minn = l;
else if (ck(r) == 0) minn = r;
else minn = -1;
//================================
l = 1, r = rmax;
while(l + 1 != r)
{
mid = (l + r) >> 1;
int st = ck(mid);
if (st != -1)
l = mid;
else r = mid;
}
if (ck(r) == 0) maxn = r;
else if (ck(l) == 0) maxn = l;
else maxn = -1;
//================================
if (maxn == -1 && minn == -1)
{
cout << -1 << endl;
return 0;
}
cout << minn << ' ' << maxn << endl;
}
navigate_before
Bash On Windows
[COGS 172][IOI 2000] 回文词
navigate_next