【题解】LuoGu2207：Photo

原题传送门
按照左端点排序后，开两个指针$l,r$逐渐缩小，最多做$k$次，时间 O ( k 2 ) O(k^2) O(k2)

Code：

#include 
#define maxn 1010
using namespace std;
struct node{int x, y;
}a[maxn];
int n, m;inline int read(){int s = 0, w = 1;char c = getchar();for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);return s * w;
}bool cmp(node x, node y){ return x.x < y.x; }int main(){n = read(), m = read();for (int i = 1; i <= m; ++i){a[i].x = read(), a[i].y = read();if (a[i].x > a[i].y) swap(a[i].x, a[i].y);}sort(a + 1, a + 1 + m, cmp);int l = 1, r = n, ans = 0;while (l <= n){for (int i = 1; i <= m; ++i)if (a[i].x >= l && a[i].y <= r) r = a[i].y - 1;++ans, l = r + 1, r = n;}printf("%d\n", ans);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！