ZOJ - 3953 Intervals——贪心

ZOJ - 3953 Intervals——贪心

#include #include #include #include #include using namespace std;const int maxn = 1e5 + 10;int T, n;struct Interval { int id, l, r;}a[maxn], b[10];bool cmpl(Interval &x, Interval &y) { return x.l < y.l;}bool cmpr(Interval &x, Interval &y) { return x.r > y.r;}vector ans;bool judge(Interval t[3]) { for (int i = 1; i <= 3; i++) { int x = i, y = i%3+1; if (t[x].r < t[y].l || t[x].l > t[y].r) return false; } return true;}int main() { scanf("%d", &T); while (T--) { scanf("%d", &n); for (int i = 1; i <= n; i++) { a[i].id = i; scanf("%d %d", &a[i].l, &a[i].r); } sort(a + 1, a + 1 + n, cmpl); ans.clear(); b[1] = a[1]; b[2] = a[2]; for (int i = 3; i <= n; i++) { b[3] = a[i]; sort(b+1, b+4, cmpr); if (judge(b)) { ans.push_back(b[1].id); swap(b[1], b[3]); } } sort(ans.begin(), ans.end()); int len = ans.size(), flag = 0; printf("%d\n", len); for (int i = 0; i < len; i++) { if (flag++) printf(" "); printf("%d", ans[i]); } printf("\n"); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。