山东财经大学新生赛暨天梯赛选拔赛 D 流星雨 (区间贪心)

绝地灬酷狼 2022-03-07 09:20 183阅读 0赞

链接：[https://ac.nowcoder.com/acm/contest/547/D][https_ac.nowcoder.com_acm_contest_547_D]  
来源：牛客网

## 题目描述 ##

英仙座流星雨（学名Perseids）是以英仙座γ星附近为辐射点出现的流星雨，也称英仙座γ流星雨。每年在7月20日至8月20日前后出现，于8月13日达到高潮。与象限仪座流星雨、双子座流星雨并称为北半球三大流星雨。

暑假到了，又是一个去看流星雨的好季节。

看流星雨最重要的是什么？当然是许愿。

当一颗流星出现时，可以对其许愿。

你一次可以选择一颗流星进行许愿，每一个愿望都需要一定的时间才能说完，而且中间不能有中断。

但是流星的持续时间通常都很短，很难在流星消失之前把自己的一个愿望说完。

你可以朝着新出现的流星接着许上一个未许完的愿望，当且仅当前一颗流星消失的瞬间另外一颗流星同时出现，

你不可以在一颗流星还在出现的时候转向其他的流星，这样流星之神会生气，厄运会降临

现在给你每颗流星出现和结束的时间，问你许一个愿望的最大时长是多少？

## 输入描述: ##

第一行一个数n n<=1000000
    
    表示流星的数目
    
    接下来每行2个数字 x，y （0<x,y<=1000000）
    
    表示流星出现的时间和结束的时间

## 输出描述: ##

一个数字，表示最长可以连续许愿的时间

示例1

## 输入 ##

复制

3
    2 3
    2 4
    1 2

## 输出 ##

复制

## 说明 ##

1~4

#include<iostream>
    #include<algorithm>
    using namespace std;
    
    int ans[1000000+10]={0};
    struct AC
    {
    	int x,y;
    }a[1000000+10];
    
    bool cmp(AC c,AC d)
    {
    	return c.y<d.y;
    }
    int main()
    {
    	int n,m,j,k,i,T;
    	cin>>n;
    	for (i=0;i<n;i++)
    	cin>>a[i].x>>a[i].y;
    	
    	sort(a,a+n,cmp);
    	int Max=-100;
    	for (i=0;i<n;i++)
    	{
    		ans[a[i].y] = max(ans[a[i].y] , ans[a[i].x]+a[i].y-a[i].x);
            if (ans[a[i].y]>Max)
    		Max = ans[a[i].y];
    	}
    	
    	
    	cout<<Max<<endl;
    	return 0;
    }

[https_ac.nowcoder.com_acm_contest_547_D]: https://ac.nowcoder.com/acm/contest/547/D