首页 > 代码库 > 线段覆盖
线段覆盖
【题目描述】
在一个数轴上有n(n <= 1000000)条线段，每条线段的两端可用整数坐标表示，坐标范围为[0,1018]，每条线段都有一个价值Ci(0 <= Ci <= 109)，请从n条线段中选出若干条线段，使得这些线段两两不覆盖（端点可以重合）且线段价值之和最大。
【输入描述】
第一行输入一个整数n，表示有多少条线段；
接下来n行，每行输入三个整数Ai、Bi、Ci，分别代表第i条线段的左端点、右端点（左端点 < 右端点）和价值。
【输出描述】
输出一个数，表示能够获得的最大价值。
【样例输入】
3
1 2 1
2 3 2
1 3 4
【样例输出】
4
#include<cstdio>#include<algorithm>using namespace std;struct Node{ unsigned long long L,R,S;}i[1000001];unsigned long long f[1000001]={0};int n;bool Rule(Node t1,Node t2){ return t1.R<t2.R;}int Find(int t){ int Left=0,Right=t-1,Mid=0; while (Left+1<Right) { Mid=(Left+Right)>>1; if (i[Mid].R>i[t].L) Right=Mid; else Left=Mid; } if (i[Right].R<=i[t].L) return Right; else return Left;}int main(){ scanf("%d",&n); for (int a=1;a<=n;a++) scanf("%lld%lld%lld",&i[a].L,&i[a].R,&i[a].S); sort(i+1,i+n+1,Rule); for (int a=1;a<=n;a++) f[a]=max(f[a-1],f[Find(a)]+i[a].S); printf("%lld",f[n]); return 0;}
线段覆盖
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。