题目描述
看到还没题解,那我来更一篇!
大家自己去看题目和样例叭,应该很好理解
Solution
自动刷题机TT(蒟蒻也好想拥有),可惜目前不存在,留着给以后的oier发明吧;
这是本蒟蒻第一次做SHOI,发现在洛谷上是道好水的蓝题
题目大意就是让你求一个最小值n和一个最大值n满足题意能恰好A掉k题;
我们会发现 当n越大的时候 A掉的题目会越少(这很显然吧,想想看写个巨长的代码,直接交不是很难A成功
当然和题目不是一个意思扯偏了)
反之亦然,也就是这道题是满足单调性的;
首先我们肯定会想到暴力,直接枚举n很显然会超时
那么既然满足单调性,我们自然就想到二分答案
我们可以用一个check函数来判断,check(x)表示当n=check的时候我们能做几题呢
对于求最小值n而言
当check(mid)>k时,说明我们做的太多了,那么这时候我们就让他小一点,也就是把mid调大,很显然l=mid+1;
如果check(mid)<k,那就把mid调小,这样A的就多了,r=mid-1;
如果check(mid)=k,直接满足题意,那么我们就把ans=mid,作为备选答案,这时候处理左区间就好啦,即r=mid-1(因为你要的是n的最小值)
反之,对于求最大值而言,我们只需要把第3步中的处理左区间改为右就好啦,即l=mid+1;
然后这题就做完啦
说一下几个细节
1.l初始为1,r初始为无穷大,答案也是无穷大
2.当答案不为无穷大也就是有答案时 那么输出答案;反之如果没有,就直接输出-1(这一步直接在求最小值中体现,因为如果最小值都没有答案,最大值就更没有了,思考下为什么)
3.不开longlong见祖宗
参考文献
出自 这是我的博客
My code
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+15;
#define int long long
int a[maxn],l,k,r,n,ans;
int check(int x)
{
int num=0,len=0;
for(register int i=1;i<=n;++i)
{
num+=a[i];
if(num<0) num=0;
if(num>=x) num=0,len++;
}
return len;
}
signed main()
{
scanf("%lld%lld",&n,&k);
for(register int i=1;i<=n;++i)
{
scanf("%lld",&a[i]);
}
l=1,r=1e15;
ans=1e15+1;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid)>k) l=mid+1;
else if(check(mid)<k) r=mid-1;
else ans=mid,r=mid-1;
}
if(ans!=1e15+1) printf("%lld ",ans);
else
{
printf("-1");
return 0;
}
l=1,r=1e15;
ans=1e15+1;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid)>k) l=mid+1;
else if(check(mid)<k) r=mid-1;
else ans=mid,l=mid+1;
}
printf("%lld\n",ans);
return 0;
}
TT原谅我的码风,它太不好看了QAQ
校友校友
写的真好