链接：

https://ac.nowcoder.com/acm/contest/924/G

题意：

Farmer John has returned to the County Fair so he can attend the special events (concerts, rodeos, cooking shows, etc.). He wants to attend as many of the N (1 <= N <= 10,000) special events as he possibly can.

He's rented a bicycle so he can speed from one event to the next in absolutely no time at all (0 time units to go from one event to the next!).

Given a list of the events that FJ might wish to attend, with their start times (1 <= T <= 100,000) and their durations (1 <= L <= 100,000), determine the maximum number of events that FJ can attend. FJ never leaves an event early.

思路：

将持续时间改变成结束时间，然后直接按照结束时间贪心即可。

代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int MAXN = 1e5 + 10;

const int MOD = 1e9 + 7;

int n, m, k, t;

struct Node

{

    int l, r;

    bool operator < (const Node & that) const

    {

        if (this->r != that.r)

            return this->r < that.r;

        return this->l > that.l;

    }

}node[MAXN];

int main()

{

    cin >> n;

    for (int i = 1;i <= n;i++)

    {

        cin >> node[i].l >> node[i].r;

        node[i].r += node[i].l;

    }

    sort(node+1, node+1+n);

    int last = 0, res = 0;

    for (int i = 1;i <= n;i++)

    {

        if (node[i].l >= last)

            res++, last = node[i].r;

    }

    cout << res << endl;

    return 0;

}

巴特西

牛客假日团队赛2 G.CountyFairEvents

链接：

题意：

思路：

代码：

最新文章

热门文章