前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Codeforces 976C 题解报告

Codeforces 976C 题解报告

作者头像
海天一树
发布2018-07-25 14:20:19
3050
发布2018-07-25 14:20:19
举报
文章被收录于专栏:海天一树

一、题目

http://codeforces.com/contest/976/problem/C

二、思路

对数据进行排序: (1)按左边的数从小到大排; (2)若左边的数相等,则按右边的数从大到小排。

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

代码语言:javascript
复制
2 13
2 12
1 11

排序之后,变为

代码语言:javascript
复制
1 11
2 13
2 12

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

三、代码

代码语言:javascript
复制
#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;
}

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2018-05-03,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 海天一树 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、题目
  • 二、思路
  • 三、代码
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档