学长给的题,写完之后看题解貌似没有人和我的情况一样,就来写一波

思路

考虑每一个划分都可以由一个二元组来解释 $ (len, la) $

其中

  • $len$ 为长度
  • $la$ 为最后一个数字

那么现在有一个数字 $a$ ,我们要接到任意一个划分后面

一个必要条件是 $ la + 1 = a $

那么筛选下来的每个二元组的差别就只有 $len$ 了,显然优先接到较短的后面即可

实现

先将 $a$ 数组排序

建立一个以 $(len,la)$ 节点, $len$ 为关键字 $len$ 越小越在上面的堆 $q$

然后从 $a_i$ 遍历到 $a_n$

每一次从堆 $q$ 中取出顶部节点,如果合法,放入 $tmp$ 队列

不合法,更新 $ans$ 后舍弃即可

遇到 $ a_i \neq a_i + 1 $ 的情况,将 $tmp$ 内容放入堆 $q$

最后将 $tmp$ 内容清空并更新 $ans$

代码

以下代码在 https://www.luogu.com.cn/record/29511205 中提交 并 AC

#include <cstdio>

#include <queue>
#include <algorithm>

inline int Min( int a, int b ) { return a < b? a: b; }
int readin() {
    int res = 0; char x = getchar();
    while( x < '0' || x > '9' ) 
        x = getchar();
    while( x >= '0' && x <='9' ) {
        res = res * 10 + ( x - '0' );
        x = getchar();
    }
    return res;
}

const int N = 1e5 + 1e4;

struct node {
    int len, la;
    bool operator< ( const node &b ) const{
        return this -> len > b.len;
    }
};

int n, ans;
int a[N];
std::priority_queue<node> q;
std::queue<node> tmp;

int main() {
#ifdef woshiluo
    freopen( "luogu.4447.in", "r", stdin );
    freopen( "luogu.4447.out", "w", stdout );
#endif
    n = readin();
    ans = n;
    for( int i = 1; i <= n; i ++ ) {
        a[i] = readin();
    }

    std::sort( a + 1, a + n + 1 );

    for( int i = 1; i <= n; i ++ ) {
        if( a[i] != a[ i - 1 ] && i != 1 ) {
            while( tmp.empty() == false ) {
                q.push( tmp.front() );
                tmp.pop();
            }
        }
        bool flag = false;
        while( q.empty() == false ) {
            node top = q.top(); q.pop();
            if( top.la + 1 == a[i] ) {
                flag = true;
                tmp.push( (node) { top.len + 1, a[i] } );
                break;
            }
            else
                ans = Min( ans, top.len );

        }
        if( !flag ) 
            tmp.push( (node) { 1, a[i] } );
    }

    while( tmp.empty() == false ) {
        q.push( tmp.front() );
        tmp.pop();
    }

    while( q.empty() == false ) {
        node top = q.top(); q.pop();
        ans = Min( ans, top.len );
    }

    printf( "%d\n", ans );
}