AT_utpc2020_a题解

· · 题解

题意简化

查找一个最小可以走完全程的初始体力值。

需要注意的地方

  1. 暴力算法过不了，要用更好的算法。
  2. 记得开 long long 以防止溢出。

解法分析

一级解法

直接循环枚举。

#include<bits/stdc++.h>
using namespace std;
long long n,l;
long long x[200009],a[200009];
bool ok(long long xx){//判断条件 
    long long now=xx;
    for(int i=1;i<=n;i++){
        now=now+x[i]-x[i-1];
        if(now>xx) now=xx;//大于上限就设为上限 
        now-=a[i];
        if(now<0) return 0;//寄了 
    }
    return 1;
}
int main(){
    cin>>n>>l;
    for(int i=1;i<=n;i++){
        scanf("%d %d",&x[i],&a[i]);
    }
    long long i=0;
    while(1){//无限循环 
        if(ok(i)==1){//找到了答案，结束 
            cout<<i;
            return 0;
        }
        i++;
    }
    return 0;
}

但是很显然，这种做法跟暴力搜索几乎没有区别，都会超时。这只是一级解法，能过掉 a[i] 比较小的数据。

二级解法

有经验的选手对于这种题目，一眼就知道这道题是一个典型的二分，因为它具有单调性。

前置知识：单调性与二分（可直接跳过）

什么是单调性？举个不恰当的例子，你想把老师气到极限，一旦老师气愤值过了极限你就完了，但没达到极限值你又不满意，就形成了一种很尴尬的局面：你想满足自己，不能比极限值少一点或多一点（你就完了），必须刚好在老师气愤值极限。这就是单调性。

我们试研究这道题的单调性：你的体力值少一点，你就寄在半路上了；你体力值多一点，不满足题目最小值的要求。所以，这道题目有单调性，即可以用二分解决。

那什么是二分？比如你想查找严格单调递增的数组中比某个特定值大的最小数，正常情况直接枚举，如果想更优就可用二分方法。下面是二分的图解（我们并不分析它的实现，只是学习思想）：

可以看到，每次都将选择部分分成两份，判断条件，继续查找。

我们就有以下的二分板子：

while(l<=r){
    int mid=(l+r)/2;
    if(条件成立){
        ans=mid;
        r=mid-1;
    }
    else l=mid+1;
}

这个板子可以解决很多二分问题。

用到二分或它的思想的题其实蛮多的，比如归并排序、快速排序、堆等等。

知识讲解完毕

回到问题，我们发现这道题可以做二分后，就能对一级解法的代码进行修改，只要把：

while(1){//无限循环 
        if(ok(i)==1){//找到了答案，结束 
            cout<<i;
            return 0;
        }
        i++;
    }

改成：

while(l<=r){
        long long mid=(l+r)/2;//计算mid 
        if(ok(mid)==1){//找到了答案（可能不是结果） 
            ans=mid;
            r=mid-1;//将上限往左移 
        }
        else l=mid+1;//将下限往右移 
    }

这样的做法效率很高，可以从 O(n) 升级到 O(\log{n}) 的时间复杂度。

如果想让你的二分主体更好，可以改成这样：

while(l<=r){
    long long mid=l+((r-l)>>1);//计算mid 
    if(ok(mid)==1){//找到了答案（可能不是结果） 
        ans=mid;
        r=mid-1;//将上限往左移
    }
    else l=mid+1;//将下限往右移 
}

这样不仅能解决 mid 溢出的问题，还能加快运算速度（使用了位运算）。

最后说一句，我比较推荐万能头文件，这样可以省去很多不必要的麻烦。

完整代码

//已通过 
#include<bits/stdc++.h>
//万能头文件
using namespace std;
long long n,l,sum,ans;
long long x[200009],a[200009];
bool ok(long long xx){//判断条件 
    long long now=xx;
    for(int i=1;i<=n;i++){
        now=now+x[i]-x[i-1];
        if(now>xx) now=xx;//大于上限就设为上限 
        now-=a[i];
        if(now<0) return 0;//寄了 
    }
    return 1;
}
int main(){
    cin>>n>>l;
    for(int i=1;i<=n;i++){
        scanf("%d %d",&x[i],&a[i]);
        sum+=a[i];
    }
    long long l=0,r=sum;
    while(l<=r){
        long long mid=(l+r)/2;//计算mid 
        if(ok(mid)==1){//找到了答案（可能不是结果） 
            ans=mid;
            r=mid-1;//将上限往左移
        }
        else l=mid+1;//将下限往右移 
    }
    cout<<ans;
    return 0;
}