CSP-S模拟-B.选择人员

我真的要死了，tmd考场上思路是对的，但是因为实现太狗屎且没有大样例导致莫名其妙的爆$0$了！！！

依次寻找每组最小的$c[i]$个数，这里我们易得排序后每组中选择连续的一段一定比选择分离的几段更优

每组记录一个指针分开来跳，总的复杂度是$O(n\sum_{i=1}^n m[i])$

考虑优化路径，思考一下可以发现我们没有必要每个数组都记录一个指针，我们只关注两个条件

<1>当前的选择数中的最小值和最大值

<2>选择的数有没有满足选择的个数

所以我们可以合并整个序列后排序，然后双指针枚举记录答案就可以了

时间复杂度$O(m\times log(m))$，瓶颈在于排序带的$log$

#include<bits/stdc++.h>
using namespace std;
#define pii pair< int,int >
#define val first
#define idx second

const int N=1e5+10;

int m[N], c[N];
vector< pii > h;

int operator -( const pii &a,const pii &b ){ return a.val-b.val; }

int main()
{
//	freopen( "military.in","r",stdin );
//	freopen( "military.out","w",stdout );
	ios::sync_with_stdio( false );
	cin.tie( nullptr ), cout.tie( nullptr );
	int n, m;
	cin>>n;
	for( int i=1;i<=n;i++ )
	{
		cin>>m>>c[i];
		for( int j=1;j<=m;j++ )
		{
			int x;
			cin>>x;
			h.push_back( { x,i } );
		}
	}
	sort( h.begin(),h.end() );
	int ans=INT_MAX;
	m=n, n=h.size();
	for( int l=1, r=1;l<=n;l++ )
	{
		while( m && r <= n )
		{
			c[h[r].idx]--;
			if( c[h[r].idx] == 0 ) m--;
			r++;
		}
		if( m && r == n+1 ) break;
		ans=min( ans,h[r-1]-h[l] );
		if( !c[h[l].idx] ) m++;
		c[h[l].idx]++;
	}
	cout<<ans;
}