华师一附中OI组

标题: NOIP 2016 D2T2 蚯蚓 [打印本页]

---

作者: 胡雨菲菲    时间: 2018-6-12 16:18
标题: NOIP 2016 D2T2 蚯蚓
本题中，我们将用符号 LcJ 表示对 c 向下取整，例如： L3.0J = L3.1J = L3.9J = 3 。 蛐蛐国最近蚯蚓成灾了！隔壁跳蚤国的跳蚤也拿蚯蚓们没办法，蛐蛐国王只好去 请神刀手来帮他们消灭蚯蚓。
蛐蛐国里现在共有 n 只蚯蚓（ n 为正整数）。 每只蚯蚓拥有长度，我们设第 i 只匠 蚓的长度为 ai ( i = 1, 2, … , n )，并保证所有的长度都是非负整数（即：可能存在长度为 0 的蚯蚓）。
每一秒，神刀手会在所有的蚯蚓中，准确地找到最长的那一只（如有多个则任选 一个）将其切成两半。 神刀手切开蚯蚓的位置由常数 p （是满足 0 < p < 1 的有理数） 决定，设这只蚯蚓长度为 x ，神刀手会将其切成两只长度分别为 LpxJ 和 x − LpxJ 的匠 蚓。特殊地，如果这两个数的其中一个等于 0 ，则这个长度为 0 的蚯蚓也会被保留。此 外，除了刚刚产生的两只新蚯蚓，其余蚯蚓的长度都会增加q（是一个非负整常数）。
蛐蛐国王知道这样不是长久之计，因为蚯蚓不仅会越来越多，还会越来越长。蛐蛐国王决定求助于一位有着洪荒之力的神秘人物，但是救兵还需要 m 秒才能到来… … （ m 为非负整数）
蛐蛐国王希望知道这 m 秒内的战况。 具体来说，他希望知道： • m 秒内，每一秒被切断的蚯蚓被切断前的长度（有 m 个数）： • m 秒后，所有蚯蚓的长度（有 n + m 个数）。 蛐蛐国王当然知道怎么做啦！ 但是他想考考你… …

---

作者: 胡雨菲菲    时间: 2018-6-12 16:18
堆会超时，用三个队列即可

1. #include <cstdio>
   
2. #include <queue>
   
3. #include <algorithm>
   
4. typedef long long LL;
   
5. const int N = 100010;
   
6. const LL INF = 1ll << 62;
   
7. std::queue<LL> a;
   
8. std::queue<LL> b;
   
9. std::queue<LL> c;
   
10. 
    
11. int m, n, v, u, k, q;
    
12. LL d[N], delta;
    
13. 
    
14. inline void geta(LL &t) {
    
15.     t = a.front();
    
16.     a.pop();
    
17.     return;
    
18. }
    
19. inline void getb(LL &t) {
    
20.     t = b.front();
    
21.     b.pop();
    
22.     return;
    
23. }
    
24. inline void getc(LL &t) {
    
25.     t = c.front();
    
26.     c.pop();
    
27.     return;
    
28. }
    
29. 
    
30. int main() {
    
31.     scanf("%d%d%d%d%d%d", &n, &m, &q, &u, &v, &k);
    
32.     for(int i = 1; i <= n; i++) {
    
33.         scanf("%lld", &d[i]);
    
34.     }
    
35.     std::sort(d + 1, d + n + 1);
    
36.     for(int i = n; i >= 1; i--) {
    
37.         a.push(d[i]);
    
38.     }
    
39.     for(int i = 1; i <= m; i++) {
    
40.         LL t;
    
41.         if(b.empty() && c.empty()) {
    
42.             geta(t);
    
43.         }
    
44.         else if(a.empty()) {
    
45.             if(b.front() >= c.front()) {
    
46.                 getb(t);
    
47.             }
    
48.             else {
    
49.                 getc(t);
    
50.             }
    
51.         }
    
52.         else {
    
53.             if(a.front() >= b.front() && a.front() >= c.front()) {
    
54.                 geta(t);
    
55.             }
    
56.             else if(b.front() >= c.front()) {
    
57.                 getb(t);
    
58.             }
    
59.             else {
    
60.                 getc(t);
    
61.             }
    
62.         }
    
63.         t += delta;
    
64.         if(i % k == 0) {
    
65.             printf("%lld ", t);
    
66.         }
    
67.         LL t1 = t * u / v;
    
68.         LL t2 = t - t1;
    
69.         delta += q;
    
70.         t1 -= delta;
    
71.         t2 -= delta;
    
72.         b.push(t1);
    
73.         c.push(t2);
    
74.     }
    
75.     puts("");
    
76.     a.push(-INF);
    
77.     b.push(-INF);
    
78.     c.push(-INF);
    
79.     for(int i = 1; i <= m + n; i++) {
    
80.         LL t;
    
81.         if(a.front() >= b.front() && a.front() >= c.front()) {
    
82.             geta(t);
    
83.         }
    
84.         else if(b.front() >= c.front()) {
    
85.             getb(t);
    
86.         }
    
87.         else {
    
88.             getc(t);
    
89.         }
    
90.         if(i % k == 0) {
    
91.             printf("%lld ", t + delta);
    
92.         }
    
93.     }
    
94.     return 0;
    
95. }
    

复制代码

---

欢迎光临 华师一附中OI组 (http://hsyit.cn/)

Powered by Discuz! X3.2