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

### 序 学长给的题，写完之后看题解貌似没有人和我的情况一样，就来写一波 ### 思路 考虑每一个划分都可以由一个二元组来解释 $ (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 ```cpp #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 ); } ```