wordpress分类信息模板下载/seo外链发布平台

P1803 凌乱的yyy

①首先需要按照区间的右端点值把全部区间从小到大排序，

排序目的：保证了先选择较小的区间，进而保证选出的区间数量最多

②一定要从第一个区间开始遍历。为什么是第一个呢？（设区间为(a1,b1),(a2,b2)…）

先清楚一点，如果这个区间包含了下个区间，那么选择这个区间不如选择下一个区间划算，选下个区间还能节省几个点来用于其他区间的选择。然后就可以分为两种情况：

1. a1>a2，此时就符合了上面说的情况，一定会选1而不选2，经归纳，后面任意相邻两组出现了这种情况都要选前一个。因此无需考虑像后一个的这种区间。

2. 排除了1.中的情况，剩余的区间全部为a1<a2，b1<b2，这时候显而易见要选1

   综上，选1合适。

③选完第一个区间之后，接下来就找不与前一个区间相交的下一个区间，因此需要记录一下前一个区间的右端点。

④用循环遍历一遍数组即可出结果！

ac代码如下：

#include<iostream>
#include<algorithm>
using namespace std;
struct v {int a, b;
}vv[1000010];
bool cmp(v x, v y) {return x.b < y.b;
}
int main() {int n, ans = 1;cin >> n;for (int i = 1; i <=n; i++)cin >> vv[i].a >> vv[i].b;sort(vv + 1, vv + 1 + n, cmp);int cnt = vv[1].b;for (int i = 2; i <= n; i++){if (vv[i].a >= cnt){ans++;cnt = vv[i].b;}}cout << ans;return 0;
}