[Leaf] [P2827] 蚯蚓

luogu-p2827-蚯蚓">Luogu-P2827 蚯蚓

1. 题面梗概

中译中: 有一堆蚯蚓，每次抓出最长的一根切成两段（比例固定）。切开的同时，没被切的蚯蚓都在变长。问你切的时候的长度，以及最后所有蚯蚓的长度。

难点: 蚯蚓数量随切分不断增加，且全员增长。如果用堆（优先队列），复杂度 $O( M \log(N+M) )$，在 $7 \cdot 10^6$ 的数据下会跑死。

2. 逻辑推导

直觉起步：全员增长怎么处理？ 如果我们每切一次都要把剩下的蚯蚓都加一个 $q$，那复杂度直接爆炸。

技巧：全局偏移量 (Offset)。我们记录一个 delta 表示累计增长了多少。每次切出的新蚯蚓，入队时减去这个 delta 来抵消时差。

2.1 建模

考虑到完全依赖于堆，这题复杂度会爆炸，我们观察切分的逻辑：

• 设两根蚯蚓的长度分别为 $L_1, L_2$，且 $L_1 > L_2$。
• 在时间 $t_1$ 切断 $L_1$，得到 $pL_1$ 和 $L_1 - pL_1$。
• 在时间 $t_2$ 切断 $L_2$，得到 $p(L_2 + q \Delta t)$ 和 $(L_2 + \Delta t) - p(L_2 + q \Delta t)$。
• 结论：先切开的蚯蚓分段，永远比后切开的同比例分段长！

我们发现了一条隐含的单调性，既然如此，就不要堆来维护了。

2.2 单调队列

我们维护三个队列，且保证它们内部都是单调递减的：

1. qs[0] 初始蚯蚓，排序后具有单调性的。
2. qs[1] 所有被切开的第一段蚯蚓。
3. qs[2] 所有被切开的第二段蚯蚓。

那么我们只需要在这三个队列中找最长的蚯蚓即可。

3. 代码实现

▶

AcCode

// P2827 [NOIP2016] 蚯蚓#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<int, int>;

const int maxn = 1e5 + 50;
const int inf = 0x3f3f3f3f;

int n, m, q, u, v, t;
deque<int> qs[3];
int a[maxn], offset;

int read( )
{
    int x = 0, f = 1;
    char ch = getchar( );
    while( ch < '0'|| ch > '9' )
    {
        if( ch == '-' ) f = -1;
        ch = getchar( );
    }
    while( '0' <= ch && ch <= '9' )
    {
        x = x * 10 + ch - '0';
        ch = getchar( );
    }
    return x * f;
}

void find( int &idx, ll &val )
{
    for( int j = 0; j < 3; ++ j )
    {
        if( qs[j].empty( ) ) continue;
        if( qs[j].front( ) > val )
        {
            val = qs[j].front( );
            idx = j;
        }
    }
}

int main( )
{
    n = read( ); m = read( ); q = read( );
    u = read( ); v = read( ); t = read( );

    for( int i = 1; i <= n; ++ i )
    {
        a[i] = read( );
    }

    sort( a + 1, a + n + 1, greater<int>( ) );
    for( int i = 1; i <= n; ++ i )
    {
        qs[0].push_back( a[i] );
    }

    for( int i = 1; i <= m; ++ i )
    {
        int idx = -1;
        ll val = -inf;
        
        find( idx, val );

        qs[idx].pop_front( );
        ll real = val + offset;

        ll left = real * u / v;
        ll right = real - left;
        
        qs[1].push_back( left - (offset + q) );
        qs[2].push_back( right - (offset + q) );
        
        offset += q;
        if( i % t == 0 ) cout << real << " ";
    }
    cout << '\n';
    for( int i = 1; i <= n + m; ++ i )
    {
        int idx = -1;
        ll val = -inf;
        
        find( idx, val );

        qs[idx].pop_front( );
        if( i % t == 0 ) cout << val + q * m << " ";
    }
    return 0;
}

4. 复盘

• 复杂度: $O( N \log N + M )$。瓶颈在排序 $O(N \log N)$。

• 碎碎念: 这题的思路要求我们二次降维，当我们发现 $O(N \log N)$ 复杂度还是不够优时，就需要从寻找隐含单调性入手了。

• 关联笔记: 单调队列