HDU 6301 Distinct Values——优先队列

HDU 6301 Distinct Values——优先队列

题意：

Chiaki has an array of nn positive integers. You are told some facts about the array: for every two elements aiai and ajaj in the subarray al..ral..r(l≤i

思路：

区间按左端点排序，拿优先队列维护一下当前可用元素就可以了，细节比较多

#include #include #include #include #include #include using namespace std;const int maxn = 1e5 + 10;struct Interval { int l, r; bool operator < (const Interval &t) { if (l != t.l) return l < t.l; return r > t.r; }}a[maxn];int b[maxn];priority_queue, greater > q;void solve() { int n, m; scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) scanf("%d%d", &a[i].l, &a[i].r); sort(a + 1, a + 1 + m); for (int i = 1; i <= n; i++) b[i] = 1; while (!q.empty()) q.pop(); for (int i = 1; i <= n; i++) q.push(i); int l = a[1].l, r = a[1].r; for (int i = l; i <= r; i++) { b[i] = q-(); q.pop(); } for (int i = 2; i <= m; i++) { if (r >= a[i].r) continue; if (r < a[i].l) { for (int j = l; j <= r; j++) q.push(b[j]); l = a[i].l, r = a[i].r; for (int j = l; j <= r; j++) { b[j] = q-(); q.pop(); } } else { for (int j = l; j < a[i].l; j++) q.push(b[j]); l = a[i].l; for (int j = r + 1; j <= a[i].r; j++) { b[j] = q-(); q.pop(); } r = a[i].r; } } printf("%d", b[1]); for (int i = 2; i <= n; i++) printf(" %d", b[i]); printf("\n");}int main() { int T; scanf("%d", &T); for (int kase = 1; kase <= T; kase++) { solve(); } return 0;}

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