原题链接：https://atcoder.jp/contests/keyence2020/tasks/keyence2020_b

此题与会议安排问题极为相似，使用贪心即可。
首先使用结构体定义每个机器人在流水线上的占用情况，代码如下：

struct ro
{
    int x;
    int l;
}robot[100001];

首先，读入的数据是每个机器人所在的位置和该机器人手臂长度，因此在读入每组数据时对数据进行预处理，只存储该机器人所占用区间的两端信息，代码如下：

int n;
    cin>>n;
    for (int i = 0; i < n;i++)
    {
        cin >> robot[i].x >> robot[i].l;
        robot[i].x -= robot[i].l;
        robot[i].l = robot[i].x + 2 * robot[i].l;
    }

那么结构体robot中每个robot[i]中的x为第i个机器人所占用的区间头，l为占用的区间尾。下面根据每个机器人所占用的区间尾从小到大排序，且区间头也做相应变化，代码如下：

int cmp(ro f,ro a)//比较函数，传入sort中  f为比较的前一数据（front），a为后一数据（after）
{
    if(f.l==a.l)//区间尾相等时
        return f.x > a.x;//则按区间头从大到小排序
    return f.l < a.l;//区间尾不相等时，将小的（更靠左的）区间尾放在前面
}
......
sort(robot, robot + n, cmp);

排序完了，拥有最前区间尾的机器人被固定选用，随后向后逐个选择机器人，当选择的机器人的区间头>=当前选到的机器人的区间尾nowend则选择该机器人，将ans++，更新nowend，继续向后选择，代码如下：

ans = 1;
nowend = robot[0].l;
for (int i = 1; i < n;i++)
{
    if(robot[i].x>=nowend)
    {
        ans++;
        nowend = robot[i].l;
    }
}

完整代码如下：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
int ans = 0,nowend;
using namespace std;
struct ro
{
    int x;
    int l;
}robot[100001];

int cmp(ro f,ro a)
{
    if(f.l==a.l)
        return f.x > a.x;
    return f.l < a.l;
}

int main()
{
    int n;
    cin>>n;
    for (int i = 0; i < n;i++)
    {
        cin >> robot[i].x >> robot[i].l;
        robot[i].x -= robot[i].l;
        robot[i].l = robot[i].x + 2 * robot[i].l;
    }
    sort(robot, robot + n, cmp);
    
    ans = 1;
    nowend = robot[0].l;
    for (int i = 1; i < n;i++)
    {
        if(robot[i].x>=nowend)
        {
            ans++;
            nowend = robot[i].l;
        }
    }
    cout << ans;
    system("pause");
    return 0;
}

本文作者：TTQ
本文链接：https://blog.ponder.fun/archives/8.html
最后修改时间：2020-01-19 11:52:54
本站未注明转载的文章均为原创，并采用 CC BY-NC-SA 4.0 授权协议，转载请注明来源，谢谢！