题解：P15024 [UOI 2020 II Stage] 修理帕萨特

· · 题解

传送门。

思路

首先不难想到贪心做法，就是将原数组按照截止日期从小到大排序，如果截止日期相等就按照投放天数从小到大排序。

聪明的小朋友这时就要提问了：\ 但是题目让我们求的是最晚要从哪一天开始投放欸，总不能暴力枚举吧，那可是 O(n^2) 的复杂度，会超时的。

你说得对，所以我们可以考虑二分答案。

我们二分最晚开始投放的天数，不难想到，如果某一天开始投放是可行的，那么要么这一天是最晚开始投放的那天，要么就还可以再晚一点。

所以如果某一天可以，我们就抬高二分的下限，否则就压低二分的上限。

那么跟据以上思路，我们就可以写代码了。

::::warning[十年 OI 一场空]{open} 不开 long long 见祖宗。 ::::

::::success[AC 代码]

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2e5+5;
ll n;
struct node
{
    ll t,d;
}a[N];
bool cmp(node x,node y)
{
    if(x.d!=y.d)return x.d<y.d;
    else return x.t<y.t;
}
bool check(ll x)
{
    for(ll i=1;i<=n;i++)
    {
        x+=a[i].t;
        if(x>a[i].d)return 0;
    }
    return 1;
}
int main()
{
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++)scanf("%lld%lld",&a[i].t,&a[i].d);
    sort(a+1,a+1+n,cmp);
    ll l=0,r=a[1].d,mid,ans;
    while(l<r)
    {
        mid=(l+r)>>1;
        if(check(mid))l=mid+1,ans=mid;
        else r=mid;
    }
    printf("%lld",ans);
    return 0;
}

::::