每周三道题 『每周三道题』是计蒜客信息学推出的周更栏目。每周,在我们都会在公众号上都会发布由简到难,共三道信息学题目,并于次日公布题解。欢迎各位同学积极踊跃地参与解题哟! 题解 可以对区间按左端点从小到大排序,左端点相同按右端点从小到大排序,记下来当前遇到的最右边的点 r ,刚开始是最左边区间的右端点,然后依次看每个区间,如果这个区间的左端点比 r 大,那中间就有空的区域了,就达不到题目要求了,否则就可以接着连上去,不过如果这个区间的右端点比 r 大,那么现在遇到的最右边的点就是这个区间的右端点了,就把 r 更新成这个区间的右端点。 标程 #include <iostream> #include <algorithm> using namespace std; struct node { int a; int b; }; bool cmp(node x, node y) { // 比较函数 if (x.a != y.a) { return x.a < y.a; } return x.b < y.b; } node p[50005]; int main() { int n, r; bool f; cin >> n; for (int i = 0; i < n; i++) { cin >> p[i].a >> p[i].b; } sort(p, p + n, cmp); // 排序 r = p[0].b; f = true; for (int i = 1; i < n; i++) { if (p[i].a > r) { // 中间有空的区域了 f = false; break; } if (p[i].b > r) { // 更新目前遇到的最右边的点 r = p[i].b; } } if (f) { cout << p[0].a << ' ' << r << endl; // 输出答案 } else { cout << 'no' << endl; } return 0; } |
|