Codeforces 976C 题解报告

一、题目

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;
}

本文分享自微信公众号 - 海天一树(gh_de7b45c40e8b)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-05-03

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Coco的专栏

一道面试题引发的对javascript类型转换的思考

对于一个好奇的切图仔来说,忍不住动手尝试了一下,看到题目首先想到的是会用到高阶函数以及 Array.prototype.reduce()。

31940
来自专栏开发与安全

从零开始学C++之异常(二):程序错误、异常(语法、抛出、捕获、传播)、栈展开

一、程序错误 编译错误,即语法错误。程序就无法被生成运行代码。 运行时错误 不可预料的逻辑错误 可以预料的运行异常 例如: 动态分配空间时...

23100
来自专栏python3

python3--迭代器,生成器

现在是从结果分析原因,能被for循环的就是"可迭代的",但是如果按常规想,for怎么知道谁是可迭代的呢?

14710
来自专栏Play & Scala 技术分享

Play For Scala 开发指南 - 第2章 Scala基本语法

29150
来自专栏desperate633

浅谈javascript中的回调函数javascript中的函数匿名函数回调函数回调函数的使用回调函数实例总结

要理解javascript中的回调函数,首先我们就要对javascript中的函数有一定的理解,所以我们先从javascript中函数谈起,讲讲它与其他语言中的...

10120
来自专栏小白的技术客栈

Python基础语法-常量与变量(重发)

昨天的文章虽然有插图,但是一个都没有显示出来,估计是天气太热,不愿意露面的缘故吧。这些都不是事,暂且不表,今天再次发布与昨天相同的文章,主要为了弥补3个插图。为...

39740
来自专栏日常学python

一文解开可迭代对象和迭代器的神秘面纱

可迭代对象和迭代器是两种不同的数据类型,它们都在我们的编程中时常可以遇到。当然他们之间也有很大的关联,接下来就让我们把它们搞定。

12440
来自专栏函数式编程语言及工具

泛函编程(3)-认识Scala和泛函编程

接着昨天的文章,再示范一个稍微复杂一点的尾递归tail recursion例子:计算第n个Fibonacci数。Fibonacci数第一、第二个数值分别是0,1...

22370
来自专栏老九学堂

最新Java高薪面试题+答案+解析!

今天老九君给大家分享一些Java面试需要的题目哟~ 01 anonymousinnerclass(匿名内部类)是否可以extends(继承)其它类,是否可以im...

47470
来自专栏黑泽君的专栏

c语言基础学习09_复合类型

============================================================================= 涉及...

21310

扫码关注云+社区

领取腾讯云代金券