BZOJ 4341 [CF253 Printer] 解题报告
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了BZOJ 4341 [CF253 Printer] 解题报告，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3110字，纯文字阅读大概需要5分钟。
内容图文
乍一看这个题好像可以二分优先度搞搞。。。
实际上能不能这么搞呢。。。？
我反正不会。。。
于是开始讲我的乱搞算法：
首先肯定要把任务按照优先度排序。
用一棵在线建点的线段树维护一个时刻是否在工作。
然后就依次插入任务，记为 i，具体而言就是二分其右端点，然后令这整个区间都变成 “工作” 的状态。
在 i 被插入之前，还要检验一下在当前情况那个神秘任务的右端点是不是题中所要求的那个。
如果是，并且 i-1 的优先度和 i 的优先度不相邻或者 i 就是最优先的任务，那么就令那个神秘任务的优先度为 i 的优先度+1。
然后把这个神秘任务插入，再来考虑任务 i。
这么写完之后发现超时了。一个点要跑 2.5s 左右。
实际上到了后面，超过 10^9 的时间是一段 1，然后才是 0。
所以这里我们只需维护这个分界点就可以了。
线段树的上界就从 10^15 变成了 10^9，比原来快了一倍。
于是就可以 AC 了。
1 #include <cstdio>
2 #include <algorithm>
3usingnamespace std;
4 typedef longlong LL;
5constint N = 50000 + 5;
6constint M = 15000000 + 5;
7constint T = 1000000000;
8 9int n, root, tot, ans_p;
10 LL end, Tend = T, owari, Ans[N];
11 12struct Segment_Tree
13{
14int l, r, sum;
15}h[M];
16 17struct Task
18{
19int s, t, p, id;
20 Task (int _s = 0, int _t = 0, int _p = 0, int _id = 0) {s = _s, t = _t, p = _p, id = _id;}
21booloperator < (const Task a) const 22 {
23return p > a.p;
24 }
25}P[N];
26 27 inline void Modify(int &x, int l, int r, int s, int t)
28{
29if (!x) x = ++ tot;
30if (l == s && r == t) h[x].sum = r - l + 1;
31if (h[x].sum == r - l + 1) return ;
32 LL mid = l + r >> 1;
33if (t <= mid) Modify(h[x].l, l, mid, s, t);
34elseif (s > mid) Modify(h[x].r, mid + 1, r, s, t);
35else Modify(h[x].l, l, mid, s, mid), Modify(h[x].r, mid + 1, r, mid + 1, t);
36 h[x].sum = h[h[x].l].sum + h[h[x].r].sum;
37}
38 39 inline LL Query(int x, int l, int r, int s, int t)
40{
41if (!x) return0;
42if (h[x].sum == r - l + 1) return t - s + 1;
43if (l == s && r == t) return h[x].sum;
44 LL mid = l + r >> 1;
45if (t <= mid) return Query(h[x].l, l, mid, s, t);
46elseif (s > mid) return Query(h[x].r, mid + 1, r, s, t);
47elsereturn Query(h[x].l, l, mid, s, mid) + Query(h[x].r, mid + 1, r, mid + 1, t);
48}
49 50inline LL Calc(Task x)
51{
52int need = x.t;
53int blank = T - x.s + 1 - Query(1, 0, T, x.s, T);
54if (blank < need) return need - blank + Tend;
55int l = x.s, r = T;
56while (l < r)
57 {
58int mid = l + r >> 1;
59 blank = mid - x.s + 1 - Query(1, 0, T, x.s, mid);
60if (blank < need) l = mid + 1;
61else r = mid;
62 }
63return l;
64}
65 66int main()
67{
68 scanf("%d", &n);
69for (int i = 1; i <= n; i ++)
70 {
71int s, t, p;
72 scanf("%d%d%d", &s, &t, &p);
73if (p == -1) p = 0;
74 P[i] = Task(s, t, p, i);
75 }
76 sort(P + 1, P + n + 1);
77 scanf("%lld", &end);
78 Ans[P[n].id] = end;
79for (int i = 1; i <= n; i ++)
80 {
81if (ans_p) goto deal;
82 owari = Calc(P[n]);
83if (owari + 1 == end && (i == 1 || P[i].p != P[i - 1].p - 1))
84 {
85 ans_p = P[i].p + 1;
86 Modify(root, 0, T, P[n].s, owari < T ? owari : T);
87 Tend = Tend > owari ? Tend : owari;
88 }
89 90 deal :;
91if (i == n) continue ;
92 owari = Calc(P[i]);
93 Modify(root, 0, T, P[i].s, owari < T ? owari : T);
94 Tend = Tend > owari ? Tend : owari;
95 Ans[P[i].id] = owari + 1;
96 }
97 printf("%d\n", ans_p);
98for (int i = 1; i <= n; i ++)
99 printf("%lld%c", Ans[i], i == n ? ‘\n‘ : ‘‘);
100101return0;
102 }
原文：http://www.cnblogs.com/gromah/p/5005607.html
内容总结
以上是互联网集市为您收集整理的BZOJ 4341 [CF253 Printer] 解题报告全部内容，希望文章能够帮你解决BZOJ 4341 [CF253 Printer] 解题报告所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。