题解 P4447 【[AHOI2018初中组]分组】
woshiluo
2020-01-19 22:03:27
### 序
学长给的题,写完之后看题解貌似没有人和我的情况一样,就来写一波
### 思路
考虑每一个划分都可以由一个二元组来解释 $ (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 );
}
```