[SHOI2015]自动刷题机

题目概况

题目描述

曾经发明了信号增幅仪的发明家 (SHTSC) 又公开了他的新发明：自动刷题机---一种可以自动 (AC) 题目的神秘装置。

自动刷题机刷题的方式非常简单：首先会瞬间得出题目的正确做法，然后开始写程序。

每秒，自动刷题机的代码生成模块会有两种可能的结果：

写了(x)行代码
心情不好，删掉了之前写的(y)行代码。（如果(y)大于当前代码长度则相当于全部删除。）

对于一个 (OJ)，存在某个固定的长度(n>0)，一旦自动刷题机在某秒结束时积累了大于等于(n)行的代码，它就会自动提交并 (AC) 此题，然后新建一个文件（即弃置之前的所有代码）并开始写下一题。

(SHTSC) 在某个 (OJ) 上跑了一天的自动刷题机，得到了很多条关于写代码的日志信息。

他突然发现自己没有记录这个 (OJ) 的(n)究竟是多少。

所幸他通过自己在 (OJ) 上的 (Rank) 知道了自动刷题机一共切了(k)道题，希望你计算(n)可能的最小值和最大值。

输入输出格式

输入格式

第一行两个整数(l),(k)，表示刷题机的日志一共有(l)行，一共了切了(k)题。
第二行(l)个整数(x_1,dots,x_l)。(x_i le 0)表示写了(x_i)行代码，(x_i<0)代表删除了这道题的(-x_i)行代码。

输出格式

输出两个数(a),(b)，分别代表(n)可能的最小值和最大值。如果不存在这样的(n)则输出(-1)。

输入输出样例

输入样例 #1

输出样例 #1

3 7

数据范围

对于(20\%)的数据，(n le 10)
对于(40\%)的数据，(n le 100)
对于(60\%)的数据，(n le 2000)
对于(100\%),(n le 100000),(-10^9≤x_i≤10^9)

解题报告

题意理解

自己看题目吧....

算法解析

首先我们发现这道题目,具有浓烈的二分气息.

数据范围很大,只适合(O(nlogn))级别类型的算法存活
最小和最大,总能有点二分的感觉
刷题者的第六感

综上所述,我们考虑一下这个有趣的二分算法.

首先我们来分析这道题目的二分坐标系.(我瞎编的)

我们发现,如果按照一般的二分,是无法一起找到两个左右边界点的.

没有关系,我们可以先找到最大点.

利用一般的二分算法,我们可以找到最大点.

l=0ll,r=1e17;
while(l<r)
{
	int mid=l+r+1>>1;
	if (check1(mid))
		l=mid;
	else
		r=mid-1;
}

上面这个二分函数,和我们二分查找中的找(>=x)十分类似,但是check函数使得找到的是最大的.

然后我们将边界缩放,便于找到当前最小值.

l=1ll;r=Last_ans
while(l<r)
{
	int mid=l+r>>1;
	if (check2(mid))
		r=mid;
    else
		l=mid+1;
}

为什么两次的check函数不一样啊

因为一个是找到最大的符合条件数,一个是找到最小的符合条件数.

代码解析

#include <bits/stdc++.h>
using namespace std;
const int N=100000+20;
#define int long long
int n,k,a[N],l,r,ans;
inline int check(int x,int m)
{
	int ans=0ll,cnt=0ll;
	for(int i=1; i<=n; i++)
	{
		ans+=a[i];
		ans=max(0ll,ans);
		if (ans>=x && ans)
		{
			cnt++;
			ans=0;
		}
	}
	if (m==1ll)
		return cnt>=k;//这个是找到最大的
	if (m==2ll)
		return cnt<=k;//这个是找到最小的.
	if (m==3ll)//这个是判断
		return cnt==k;
   //建议check函数要看看二分坐标系
}
inline void init()
{
	scanf("%lld%lld",&n,&k);
	for(int i=1; i<=n; i++)
		scanf("%lld",&a[i]);
	l=0ll,r=1e17;
	while(l<r)
	{
		int mid=l+r+1>>1;
		if (check(mid,1))
			l=mid;
		else
			r=mid-1;
	}
	if (!check(r,3))
	{
		puts("-1");
		return ;
	}
	ans=r;
	l=1ll;
	while(l<r)
	{
		int mid=l+r>>1;
		if (check(mid,2))
			r=mid;
		else
			l=mid+1;
	}
	printf("%lld %lld
",r,ans);
}
signed main()
{
	init();
	return 0;
}