Codeforces 976C 题解报告

柔情只为你懂 2022-05-26 13:12 143阅读 0赞

# 一、题目 #

[http://codeforces.com/contest/976/problem/C][http_codeforces.com_contest_976_problem_C]

# 二、思路 #

对数据进行排序：  
（1）按左边的数从小到大排；  
（2）若左边的数相等，则按右边的数从大到小排。

排序之后，若一个数的右边的数小于等于上一个数的右边的数，则这两个数必然符合题意。  
比如

2 13
    2 12
    1 11

排序之后，变为

1 11
    2 13
    2 12

因为12 < 13，则有<2, 12>被包含在它的上一个数<2, 13>之内。

# 三、代码 #

#include <bits/stdc++.h>
    using namespace std;
    
    #define x first
    #define y second
    typedef pair<int, int> pt;
    const int N = 300 * 1000 + 13;
    int n;
    pair<pt, int> a[N];
    
    int main()
    {
        scanf("%d", &n);
        for (int i = 0; i < int(n); i++)
        {
            scanf("%d%d", &a[i].x.x, &a[i].x.y);
            a[i].y = i + 1;
        }
    
        // 这里用到了lambda函数，[&]表示引用传递
        // 先按a.x.x从小到大排列；若a.x.x相同，则按a.x.y从大到小排列
        sort(a, a + n, [&](pair<pt, int> a, pair<pt, int> b)
                        {
                            if (a.x.x != b.x.x)
                            {
                                return a.x.x < b.x.x;
                            }
    
                            return a.x.y > b.x.y;
                        });
    
        set<pt> cur;
        for (int i = 0; i < int(n); i++)
        {
            while (!cur.empty() && cur.begin()->x < a[i].x.x)
            {
                // 若之前的数的y比当前数的x还小，则把之前的数从cur中全部移除
                // 比如之前的数为<1,5>和<2,6>，当前数<10,20>，则把<1,5>和<2,6>移除
                cur.erase(cur.begin());
            }
    
            // 经过sort排序后，当前数的x，一定大于或等于上个数的x
            // 若当前数的y，小于或等于上个数的y，则符合题意输出结果
            if (!cur.empty() && (--cur.end())->x >= a[i].x.y)
            {
                printf("%d %d\n", a[i].y, (--cur.end())->y);
                return 0;
            }
            cur.insert({a[i].x.y, a[i].y});
        }
    
        puts("-1 -1");
        return 0;
    }

> TopCoder & Codeforces & AtCoder交流QQ群：648202993  
> 更多内容请关注微信公众号  
> ![wechat\_public.jpg][wechat_public.jpg]

[http_codeforces.com_contest_976_problem_C]: http://codeforces.com/contest/976/problem/C
[wechat_public.jpg]: /images/20220526/38bbaff987464560a69bc27da1573ffc.png