更好的阅读体验

题目概况

题目描述

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

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

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

1. 写了$x$行代码
2. 心情不好，删掉了之前写的$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

4 2
2
5
-3
9

输出样例 #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$

解题报告

题意理解

自己看题目吧....

算法解析

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

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

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

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

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

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

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

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\n",r,ans);
}
signed main()
{
    init();
    return 0;
}