AT_utpc2020_a题解

· · 题解

这道题目是一道二分的板子题，所以会有比较多的二分讲解，二分大神可以跳过。

关于二分的讲解

I.What

我们的第一个问题是，什么是二分？

二分，通常是用来解决三个问题。

  1. 有序数列查找数。

  2. 答案是最大值。

  3. 答案是最小值。

但实际上，答案具有单调性的题目大多都可以二分完成。

对于 2 和 3 的问题，如果你感觉毫无头绪，很可能就是二分。

二分的思想非常容易：每次把区间一分为二，判断应该找哪边。

看上面这张图，mid 就是我们查找的位置，如果要求最大值，如果 mid 满足条件，继续搜蓝色区间，否则搜红色区间；如果求最小值，如果满足条件，搜红色区间，否则求蓝色区间。

那么我们就很容易写出一个模板：

求最小值：

int l=mn,r=mx,ans=-1;
while(l<=r){
    int mid=(l+r)>>1;
    if(check(mid))ans=mid,r=mid-1;
    else l=mid+1;
}
cout<<ans;

求最大值：

int l=mn,r=mx,ans=-1;
while(l<=r){
    int mid=(l+r)>>1;
    if(!check(mid))ans=mid,r=mid-1;
    else l=mid+1;
}
cout<<ans;

mn 表示下限，mx 表示上限。这个模板应该说是最好理解、最不容易出错的模板。墙裂建议竞赛中按照这个模板写。

现在，我们知道了什么是二分，就可以去看下一个问题了。

II.Why

那么，我们为什么要用二分呢？

我们先说一下，二分能做的题都可以用另外一种方法实现。就是用 for 循环从 mn 到 mx 枚举。

所以二分本质上是为了优化时间。

单次二分的时间复杂度为 O(\log n)，而正常枚举是 O(n)，差距会非常大。很多问题里都要用到这种思想，所以二分是我们必须掌握的基础算法。

乌克兰有一位国际水平的大神 Um_nik 有一句名言：“Stop learning useless algorithm,go and learn using binary search.”这句话的意思是：“停止学习无用的算法，去学习使用二分查找。”这说明了二分是非常重要的。

III.How

那么，这道题怎么用二分解决呢？

我们用上面的最小值模板，只要写 check 函数即可。

也就是说上面的两个模板可以过一堆题。

代码非常简单，注意要开 long long。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k,sum=0;
int c[200005],t[200005];
bool check(int heal){
    int xz=heal,sc=0;
    for(register int i=1;i<=n;i++){
        xz+=(c[i]-sc);
        sc=c[i];
        if(xz>heal)xz=heal;//体力不能超出上限
        xz-=t[i];//消耗体力
        if(xz<0)return 0;//倒下了
    }
    return 1;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(register int i=1;i<=n;i++){
        cin>>c[i]>>t[i];
        sum+=t[i];
    }
    int l=0,r=sum,ans=-1;
    while(l<=r){//二分板子
        int mid=(l+r)>>1;
        if(check(mid))ans=mid,r=mid-1;
        else l=mid+1;
    }
    cout<<ans;
}

那么，这篇题解完成了，再推荐几道二分好题。

P1577

这道题难度黄，是更简单的板子。

P1873

也是板子，黄。

P1948

这是一道蓝题，建议学习广搜或者 SPFA 最短路后再做。主要难点是图论。

P2658

这是一道绿题，需要用到二分和搜索，写起来略显复杂，但确实是一道好题。

P2249

二分查找模板题，难度橙。

ABC279D

题意翻译简单化了题目，赛时难度会更高（其实可以绿）。比较难想到二分，考验技术，难度黄。

求管理审核通过~这是我的第 23 篇题解，请大家支持~