【洛谷P1803 凌乱的yyy / 线段覆盖】/【一本通1323：活动选择】 ——贪心算法，根据结束时间结构体排序

朱雀 2022-11-12 01:39 28阅读 0赞

# [P1803 凌乱的yyy / 线段覆盖][P1803 _yyy _] #

> ## 题目背景 ##
> 
> 快 noip 了，yyy 很紧张！
> 
> ## 题目描述 ##
> 
> 现在各大 oj 上有 nn 个比赛，每个比赛的开始、结束的时间点是知道的。
> 
> yyy 认为，参加越多的比赛，noip 就能考的越好（假的）。
> 
> 所以，他想知道他最多能参加几个比赛。
> 
> 由于 yyy 是蒟蒻，如果要参加一个比赛必须善始善终，而且不能同时参加 22 个及以上的比赛。
> 
> ## 输入格式 ##
> 
> 第一行是一个整数 n ，接下来 n 行每行是 2 个整数 ![a\_i, b\_i ( a\_i<b\_i )][a_i_ b_i _ a_i_b_i]，表示比赛开始、结束的时间。
> 
> ## 输出格式 ##
> 
> 一个整数最多参加的比赛数目。
> 
> ## 输入输出样例 ##
> 
> **输入**
> 
>     3
>     0 2
>     2 4
>     1 3
> 
> **输出**
> 
>     2
> 
> ## 说明/提示 ##
> 
> 对于 ![20\\%][20] 的数据， ![n \\le 10][n _le 10]。
> 
> 对于 ![50\\%][50] 的数据， ![n \\le 10^3][n _le 10_3]。
> 
> 对于 ![70\\%][70] 的数据， ![n \\le 10^\{5\}][n _le 10_5]。
> 
> 对于 ![100\\%][100] 的数据， ![1\\le n \\le 10^\{6\}][1_le n _le 10_6] ， ![0 \\le a\_\{i\} < b\_\{i\} \\le 10^6][0 _le a_i_ _ b_i_ _le 10_6]。

同样，这道题和一本通的【活动选择】除了题面不一样，思路一模一样。

# [一本通1323：活动选择][1323] #

> ### 【题目描述】 ###
> 
> 学校在最近几天有nn个活动，这些活动都需要使用学校的大礼堂，在同一时间，礼堂只能被一个活动使用。由于有些活动时间上有冲突，学校办公室人员只好让一些活动放弃使用礼堂而使用其他教室。
> 
> 现在给出nn个活动使用礼堂的起始时间![begin\_i][begin_i]和结束时间![end\_i(begin\_i<end\_i)][end_i_begin_i_end_i]，请你帮助办公室人员安排一些活动来使用礼堂，要求安排的活动尽量多。
> 
> ### 【输入】 ###
> 
> 第一行一个整数![n(n\\le 1000)][n_n_le 1000]；
> 
> 接下来的nn行，每行两个整数，第一个![begin\_i][begin_i]，第二个是![end\_i(begin\_i<end\_i\\le 32767)][end_i_begin_i_end_i_le 32767]。
> 
> ### 【输出】 ###
> 
> 输出最多能安排的活动个数。
> 
> ### 【输入样例】 ###
> 
>     11
>     3 5
>     1 4
>     12 14
>     8 12
>     0 6
>     8 11
>     6 10
>     5 7
>     3 8
>     5 9
>     2 13
> 
> ### 【输出样例】 ###
> 
>     4

这道题明显就是贪心嘛。

但是，思路比较特殊，需要排序的是**结束时间**，不可以按照持续时间排序，要不然容易交错时间。

于是下面这个代码可以同时AC两个题目。（自己觉得码风还是挺好的，注：stable\_sort和sort是一样的）

#include <iostream>
    #include <algorithm>
    using namespace std;
    struct node
    {
        int b, e;
    };
    bool cmp(node arr, node arr1)
    {
        return arr.e < arr1.e;
    }
    int main()
    {
        int n;
        cin >> n;
        node *arr = new node[n + 10];  // 动态声明数组，减少内存，
        for (int i = 0; i < n; i++)
        {
            cin >> arr[i].b >> arr[i].e;
        }
        stable_sort(arr, arr + n, cmp);
        // cout << "_----------" << endl;
        // for (int i = 0; i < n; i++)
        // {
        //     cout << arr[i].b << " " << arr[i].e << endl;
        // }
        // cout << "_----------" << endl;
        int cnt = 1, i, j = 0;
        for (i = 0; i < n; i++)
        {
            i = j;
            // cout << "i=" << i << ";   j=" << j << endl;
            // cout << "cnt=" << cnt << endl;
            for (j = i + 1; j < n; j++)
            {
                if (arr[j].b >= arr[i].e)
                {
                    cnt++;
                    break;
                }
            }
        }
        cout << cnt << endl;
        return 0;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70][]

[P1803 _yyy _]: https://www.luogu.com.cn/problem/P1803
[a_i_ b_i _ a_i_b_i]: https://private.codecogs.com/gif.latex?a_i%2C%20b_i%20%28%20a_i%3Cb_i%20%29
[20]: https://private.codecogs.com/gif.latex?20%5C%25
[n _le 10]: https://private.codecogs.com/gif.latex?n%20%5Cle%2010
[50]: https://private.codecogs.com/gif.latex?50%5C%25
[n _le 10_3]: https://private.codecogs.com/gif.latex?n%20%5Cle%2010%5E3
[70]: https://private.codecogs.com/gif.latex?70%5C%25
[n _le 10_5]: https://private.codecogs.com/gif.latex?n%20%5Cle%2010%5E%7B5%7D
[100]: https://private.codecogs.com/gif.latex?100%5C%25
[1_le n _le 10_6]: https://private.codecogs.com/gif.latex?1%5Cle%20n%20%5Cle%2010%5E%7B6%7D
[0 _le a_i_ _ b_i_ _le 10_6]: https://private.codecogs.com/gif.latex?0%20%5Cle%20a_%7Bi%7D%20%3C%20b_%7Bi%7D%20%5Cle%2010%5E6
[1323]: http://ybt.ssoier.cn:8088/problem_show.php?pid=1323
[begin_i]: https://private.codecogs.com/gif.latex?begin_i
[end_i_begin_i_end_i]: https://private.codecogs.com/gif.latex?end_i%28begin_i%3Cend_i%29
[n_n_le 1000]: https://private.codecogs.com/gif.latex?n%28n%5Cle%201000%29
[end_i_begin_i_end_i_le 32767]: https://private.codecogs.com/gif.latex?end_i%28begin_i%3Cend_i%5Cle%2032767%29
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210321192917893.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ==,size_16,color_FFFFFF,t_70