题目链接
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3953
题意 给出N个区间，求去掉某些区间，使得剩下的区间中，任何的三个区间都不两两相交。
思路 将所有区间 以左端点为键值从小到大排序 然后三个三个一组 进行判断 如果 这三个中有两两相交的 那么就删去右端点最大的 因为这个区间对答案的贡献最小
然后三个区间当中没有两两相交的，那么下一次进来的区间就替换掉右端点最小的。
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a) memset(a, 0, sizeof(a)) #define pb push_back using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair<string, int> psi; typedef pair<string, string> pss; const double PI = 3.14159265358979323846264338327; const double E = exp(1); const double eps = 1e-30; const int INF = 0x3f3f3f3f; const int maxn = 5e4 + 5; const int MOD = 1e9 + 7; int ans[maxn]; int pos; struct Node { int id; int l, r; void read() { scanf("%d%d", &l, &r); } }q[maxn]; Node v[5]; bool comp(Node x, Node y) { return x.l < y.l; } bool comp2(Node x, Node y) { return x.r < y.r; } bool comp3(Node x, Node y) { return x.r > y.r; } void solve() { sort(v, v + 3, comp); bool flag = ((v[1].l <= v[0].r) && (v[2].l <= v[0].r) && (v[2].l <= v[1].r)); if (flag) { sort(v, v + 3, comp2); ans[pos++] = v[2].id; } else sort(v, v + 3, comp3); } int main() { int t; scanf("%d", &t); while (t--) { int n; scanf("%d", &n); for (int i = 1; i <= n; i++) { q[i].read(); q[i].id = i; } sort(q + 1, q + 1 + n, comp); v[0] = q[1]; v[1] = q[2]; pos = 0; for (int i = 3; i <= n; i++) { v[2] = q[i]; solve(); } sort(ans, ans + pos); printf("%d\n", pos); for (int i = 0; i < pos; i++) { if (i) printf(" "); printf("%d", ans[i]); } printf("\n"); } }转载于:https://www.cnblogs.com/Dup4/p/9433158.html
