(luogu2827)蚯蚓(NOIP2016TG)

发表于 | 分类于 ，

原题链接

思路:

最朴素的想法是用堆存储每条蚯蚓, 同时用一个全局变量来记录所有蚯蚓增长的长度. 但是T了.

关键之处在于发现其中的单调性: 先斩的蚯蚓长度一定比后斩的蚯蚓要长.

首先先斩的蚯蚓在斩的时候就比后斩的长, 在后斩的开斩前先斩的两段长度和增加了2k, 而后斩的只增加了k, 所以先斩的两段一定比后斩的对应段要长.

发现了单调性意味着不需要使用堆来找出最长的蚯蚓了. 排序后建立三个队列存储即可, 其中一个用于存放未斩的蚯蚓, 另外两个用于存放已斩蚯蚓的对应段.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <queue>
#include <cctype>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int Mn(100005),Mm(7000005);

template<typename T>
void qrd(T& x) {
    x = 0;
    char c = getchar();
    while(!isdigit(c)) {
        c = getchar();
    }
    while(isdigit(c)) {
        x = x*10 + (c-'0');
        c = getchar();
    }
}

int n,m;

class Queue {   //循环队列
private:
    int* arr;
    const int size;
    int head, tail;
public:
    const static int NIL = 0x80000000;
    explicit Queue(int size): size(size), head(0), tail(0) {
        arr = new int[size];
    }
    void push(int x) {
        arr[tail] = x;
        tail = (tail + 1) % size;
    }
    int front() {
        if(head == tail) {
            return NIL;
        } else {
            return arr[head];
        }
    }
    void pop() {
        head = (head + 1) % size;
    }
}org(Mn),spl1(Mm),spl2(Mm); //原长队列, 第一段, 第二段

int a[Mn];  //蚯蚓长度

int main() {
    int q,u,v,t;
    qrd(n), qrd(m), qrd(q), qrd(u), qrd(v), qrd(t);
    for(int i(1);i<=n;++i) {
        qrd(a[i]);
    }
    sort(a+1,a+n+1,[](int a,int b) -> bool { return a>b; });    //从大到小排序
    for(int i(1);i<=n;++i) {
        org.push(a[i]);
    }
    int add(0); //全局增长长度
    int mul(1); //用于记录输出
    for(int i(1);i<=m;++i) {
        int nlen = max(max(org.front(),spl1.front()),spl2.front()) + add;
        if(i==mul*t) {
            printf("%d ",nlen);
            ++mul;
        }
        //寻找并出队
        if(org.front()==nlen-add) {
            org.pop();
        } else if(spl1.front()==nlen-add) {
            spl1.pop();
        } else {
            spl2.pop();
        }
        int llen = 1ll*nlen*u/v, rlen = nlen-llen;  //斩蚯蚓
        add += q;
        spl1.push(llen-add), spl2.push(rlen-add);   //入队
    }
    printf("\n");
    while(true) {
        for(int i(1);i<t;++i) {
            int nlen = max(max(org.front(),spl1.front()),spl2.front());
            if(nlen == Queue::NIL) {
                break;
            }
            if(org.front()==nlen) {
                org.pop();
            } else if(spl1.front()==nlen) {
                spl1.pop();
            } else {
                spl2.pop();
            }
        }
        int nlen = max(max(org.front(),spl1.front()),spl2.front());
        if(nlen == Queue::NIL) {
            break;
        }
        printf("%d ",nlen+add);
        if(org.front()==nlen) {
            org.pop();
        } else if(spl1.front()==nlen) {
            spl1.pop();
        } else {
            spl2.pop();
        }
    }
    return 0;
}