NC23647. 流星雨
描述
英仙座流星雨（学名Perseids）是以英仙座γ星附近为辐射点出现的流星雨，也称英仙座γ流星雨。每年在7月20日至8月20日前后出现，于8月13日达到高潮。与象限仪座流星雨、双子座流星雨并称为北半球三大流星雨。
暑假到了，又是一个去看流星雨的好季节。
看流星雨最重要的是什么？当然是许愿。
现在给你每颗流星出现和结束的时间，问你许一个愿望的最大时长是多少？
输入描述
第一行一个数n n<=1000000
表示流星的数目
接下来每行2个数字 x，y （0<=x,y<=1001000 ）
表示流星出现的时间和结束的时间
输出描述
一个数字，表示最长可以连续许愿的时间
示例1
输入:
3 2 3 2 4 1 2
输出:
3
说明:
1~4C++14(g++5.4) 解法, 执行用时: 833ms, 内存消耗: 13520K, 提交时间: 2019-04-11 21:07:58
#include<bits/stdc++.h>
using namespace std;
int n,dp[1001005],ans;
struct node
{
int l,r;
bool operator <(const node&m)const
{
return l<m.l;
}
}k[1001005];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>k[i].l>>k[i].r;
}
sort(k+1,k+1+n);
for(int i=1;i<=n;i++)
{
dp[k[i].r]=max(dp[k[i].r],dp[k[i].l]+k[i].r-k[i].l);
ans=max(ans,dp[k[i].r]);
}
cout<<ans;
return 0;
}
C++ 解法, 执行用时: 837ms, 内存消耗: 12152K, 提交时间: 2022-02-17 16:42:52
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+7;
int ans[maxn],sum;
struct node{
int x,y;
}e[maxn];
bool cmp(node a,node b){
return a.x<b.x;
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>e[i].x>>e[i].y;
sort(e+1,e+n+1,cmp);
for(int i=0;i<=n;i++){
ans[e[i].y]=max(ans[e[i].y],e[i].y-e[i].x+ans[e[i].x]);
sum=max(sum,ans[e[i].y]);
}
cout<<sum;
}