题解 P4188 【[USACO18JAN]Lifeguards S】

· · 题解

我都不敢想象我居然能写出提高+省选-的题

这题看前面的大佬都是用线段树写的

那我就用。。比较玄学的方法写下吧 其实是因为我不会线段树

大概思路是用结构体覆盖，也可以将每一段工作时间理解为一截线段

废话不多说，上代码（思路见代码批注）~

#include <bits/stdc++.h>
using namespace std;
int n,ans,sp,m=100000000;
struct tim
{
    int l;
    int r;
}a[100010];//建立结构体，方便记录起始时间点和结束时间点
int cmp(tim x,tim y)
{
    return x.l<y.l;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&a[i].l,&a[i].r);
        sort(a+1,a+n+1,cmp);//按起始点排序
        for(int i=1;i<=n;i++)
        {
            if(a[i].r>sp)//原来记录覆盖点的末点小于当前工作结束点
            {
            int u=max(sp,a[i].l);
            //若sp大则意为新输入的这段线段的初始点在原已覆盖所有点之内
            //若a[i].l大则意为新输入的这段线段的初始点在原覆盖线段末点之外
                ans+=a[i].r-u;//加入新覆盖线段的长度
                sp=a[i].r;//更新覆盖线段末点
            }
        }
        sp=0;//一定要记得初始化！！！
        a[n+1].l=a[n].r;//建立边界，防止溢出
        for(int i=1;i<=n;i++)//求出线段对总覆盖线段的最小作用
        {
            if(a[i].r<=sp)//如果此线段的末点在总覆盖线段之内，即无作用
            m=0;
            else
            {
            int z=min(a[i+1].l,a[i].r)-max(a[i].l,sp);
            //配合代码下方的图理解
            m=min(m,z);//求出最小作用段
            sp=max(a[i].r,sp);//更新末端点，不断缩小查找范围
            }
        }
        m=max(0,m);//m不能为负数
        printf("%d",ans-m);//用总线段减去最小的作用段后，即可求出解雇一名救生员后最大的覆盖时间
    return 0;
}

好了，基本就是这样，以此较玄学方法来救助跟我一样的蒟蒻同胞们~

感觉我把一道tg+的题硬生生地写成了普及+

大佬们多多包容指教咯，完结撒花~