题解 P2827 【蚯蚓】

· · 题解

思路:

我们可以想一下，对于每一秒除了被切的哪一个所有的蚯蚓都增长Q米，我们来维护3个队列，队列1表示最开始的蚯蚓，队列2表示每一次被切的蚯蚓被分开的较长的那一部分，队列3表示每一次被切的蚯蚓被分开的较短的那一部分。

我们先把原序列排序，因为不管怎么切，先被切的蚯蚓分成的两部分一定比后切的蚯蚓分成的两部分大(较大的部分和较大的部分比较，较小的部分和较小的部分比较)，所以我们可以省去每一秒增加每只蚯蚓的长度这个操作，转换成在查询砍那只蚯蚓时，把增加的长度算到蚯蚓的总长度上。

寻找每次砍哪一只蚯蚓就是在队列1、队列2、队列3的队头找一个算上增加的长度最大的蚯蚓，之后把他出队，切开的两部分分别进入队2、队3。

对于增量的计算我们可以按照蚯蚓在队列中的标号，因为队列1中的蚯蚓直到被切是一直处于一种增长状态，所以直接加上(当前时间-1) \* Q就可以了，而对于队列2和队列3的蚯蚓，他的增长是从被切掉那一刻的下一秒开始的，所以他的增长量则是(当前时间-1-被切割的时间)\*Q。

统计答案的时候把三个队列合并，排序输出就可以了。

代码如下

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int MAXN = 1e7;
inline int read(){
    int w = 1, data = 0; char ch = 0;
    while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if(ch == '-') w = -1, ch = getchar();
    while(ch >= '0' && ch <= '9') data = data * 10 + ch - '0', ch = getchar();
    return w * data;
}
int n, Q, m, T, h[10], t[10], tmp; 
double u, v, p;
int q[4][MAXN], ans[MAXN];
inline void find(int x){
    int num = 0, sum = 0;
    for(int i = 1; i <= 3; i++){
        if(i == 1 && q[i][h[i]] + x * Q > sum && h[i] < t[i]) num = i, sum = q[i][h[i]] + x * Q;
        else if(q[i][h[i]] + (x-h[i])*Q > sum && h[i] < t[i]) num = i, sum = q[i][h[i]] + (x-h[i])*Q;
    }
    ans[x+1] = sum; tmp = sum; q[num][h[num]++];
}
int lxz[MAXN];
void Print_Ans(){
    int num = 0;

    for(int i = T, tot = 1; i <= m && tot <= m/T; i += T, tot++)
        printf("%d ",ans[i]);
    printf("\n");    

    for(int i = 1; i <= 3; i++){
        for(int j = h[i]; j < t[i]; j++){
            if(i == 1 && h[i] < t[i]) lxz[++num] = q[i][j] + (m) * Q;
            else if(h[i] < t[i]) lxz[++num] = q[i][j] + (m-j)*Q;
        }
    }
    sort(lxz+1, lxz+num+1, greater<int>());
    for(int i = T, tot = 1; i <= num && tot <= (n+m)/T; i += T, tot++)
        printf("%d ",lxz[i]);
}
int main(){
    scanf("%d%d%d%lf%lf%d", &n, &m, &Q, &u, &v, &T);
    p = u / v; 
    for(int i = 1; i <= 3; i++) h[i] = t[i] = 1; 
    for(int i = 1; i <= n; i++) q[1][i] = read(), t[1]++;

    sort(q[1]+h[1], q[1]+t[1], greater<int>());

    for(int i = 1; i <= m; i++){
        find(i-1);
        double a = floor(tmp * p), b = tmp - a;
        if(a < b) swap(a, b);
        q[2][t[2]++] = a; q[3][t[3]++] = b;
    }

    Print_Ans();
    return 0;
}