题解 P4447 【[AHOI2018初中组]分组】

· · 题解

序

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

思路

考虑每一个划分都可以由一个二元组来解释 (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 );
}