题解 AT5748 【Robot Arms】

(Solution:)

这道题基本上可以说是一道原题，详细内容参考这里，我们只需要稍微改动一部分就可以了，那就是在定义起点和终点的时候稍微算一下就可以了。那么为什么需要用每个区间的截止位置排序呢？因为当当前区间的截止为止越靠前后面留的空间也就越大，可以放下的区间也就越多，所以我们需要按每个区间的截止为止从小到大排序。

(code:)

#include<bits/stdc++.h>//万能头文件
using namespace std;//标准数据库
inline int read()//快速读入
{
    int x=0;bool f=1;char c=getchar();
    if(c==EOF) return 0;
    while(c<'0' || c>'9'){if(c=='-') f=0;c=getchar();}
    while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?x:-x;
}
struct node//定义结构体
{
    int st,ed;//记录该区域起点与终点的数值
    bool operator < (const node &x)const//重载运算符
    {
        return ed<x.ed;
        //这里一定要在该区域的结束从小到大排序，因为这样可以让更多的区域加入进来
    }
}a[100010];
int n,t,ans=1;
int main()
{
    n=read();//读入n
    for(int i=0;i<n;i++)
    {
        int x=read(),l=read();//读入 x,l
        a[i].st=x-l;//左端点
        a[i].ed=x+l;//右端点
    }
    sort(a,a+n);//排序
    t=a[0].ed;//用一个变量记录下当前可行区域的结束位置
    for(int i=1;i<n;i++)
    {
        if(a[i].st>=t)//如果下一个区间的开头大于当前区间结尾
        {
            ans++;//计数器++
            t=a[i].ed;//更新结束位置
        }
    }
    printf("%d
",ans);//输出答案，因为是AT的题，所以记得换行
    return 0;
}

如果这篇文章给予了你帮助，那你就点个赞再走吧，Thanks♪(･ω･)ﾉ

PS：这回说明不过少了吧