【贪心】线段覆盖（题解）

思路稍微变一变 切记钻牛角尖

题目描述 Description

给定x轴上的N（0<N<100）条线段，每个线段由它的二个端点a_I和b_I确定，I=1,2,……N.这些坐标都是区间（－999，999）的整数。有些线段之间会相互交叠或覆盖。请你编写一个程序，从给出的线段中去掉尽量少的线段，使得剩下的线段两两之间没有内部公共点。所谓的内部公共点是指一个点同时属于两条线段且至少在其中一条线段的内部（即除去端点的部分）。

输入描述 Input Description

输入第一行是一个整数N。接下来有N行，每行有二个空格隔开的整数，表示一条线段的二个端点的坐标。

输出描述 Output Description

输出第一行是一个整数表示最多剩下的线段数。

#include<cstdio> #include<algorithm> #include<iostream> using namespace std; struct find { int a,b; }sum[101]; bool com(struct find &x,struct find &y) { return x.a<y.a; } int main() { int n,tot=1; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d",&sum[i].a,&sum[i].b); if (sum[i].a>sum[i].b) swap(sum[i].a, sum[i].b); } sort(sum+1,sum+n+1,com); int end = sum[1].b; for (int i = 2; i <= n; i++) { if (sum[i].a >= end) { tot++; end = sum[i].b; } } printf("%d",tot); return 0; }

可以把问题简化

排掉最少的线段=保留最多的线段

本题的无后效性：是否保留 对后面的线段不产生影响 都是独立存在的个体

思路稍微变一变 切记钻牛角尖 题目描述 Description 给定x轴上的N（0 #include #include using namespace std; struct find { int a,b; }sum[101]; bool com(struct find &x,struct find &y) { return x.a sum[i].b) swap(sum[i].a, sum[i].b); } sort(sum+1,sum+n+1,com); int end = sum[1].b; for (int i = 2; i <= n; i++) { if (sum[i].a >= end) { tot++; end = sum[i].b; } } printf("%d",tot); return 0; } 可以把问题简化 排掉最少的线段=保留最多的线段 本题的无后效性：是否保留 对后面的线段不产生影响 都是独立存在的个体