题目理解

有 $N$ 个人，排名 $1$ 到 $N$。主办方有 $C$ 条列入标准，然后依次处理每条标准：就让排名最靠前且没有被列过的的 $f_i$ 个列入（如果不够，有多少列多少）。有些人会拒绝，然后就在算拒绝之后的答案。

代码思路

说白了，就是用贪心模拟列入过程。

$ve_i$：满足标准 $i$ 的所有人排名，按排名从小到大存储。

$bl_x$：$x$ 当前被哪个标准列入（$0$ 表示没有邀）。

$tot_i$：标准 $i$ 已经用到了 $ve_i$ 中的第几个人。

$vis_x$：标记 $x$ 是否拒绝（$1$ 表示拒绝）。

初始列入：

从标准 $1$ 到 $C$ 依次处理，对每个标准 $i$，从 $ve[i]$ 中依次取没有邀的人（跳过已邀的），直到取满 $f_i$ 个或列表结束。被邀人的排名加入答案 $ans$。

处理拒绝：

就按顺序依次让人 $x$ 拒绝。

如果 $x$ 之前被列入标准里（$bl_x \neq 0$），先从答案中减去 $x$，然后从原标准 $bl_x$ 开始，把别人列入准（调用 dfs($bl_x$) ）。

dfs($i$)：从标准 $i$ 的当前没有选位置 tot[i] 往后找，找到第一个没有被拒绝（$vis_t = 1$）且可以获得的人 $t$。

1. 如果 $t$ 不在任何标准里，直接将他列于此标准，更新 $bl_t=i$，答案加上 $t$，结束。

2. 如果 $t$ 在其他标准 $j$ 存在，且 $j > i$（即优先级更低的标准），则让标准 $j$ 重新找一个替补（递归 dfs($j$)），然后把 $t$ 拿过来，更新 $bl_t=i$，结束。

3. 如果（$j\le i$ 或 $vis_j=1$）跳过该人，继续往后找。

这样保证每次算完后，结果仍满足顺序。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int read(){
	int f=1,x=0;char ch;
	do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
	do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
	return x*f;
}
const int N=100005;
int a[N],f[N],viss[N],ans,vis[N],tot[N],bl[N];
vector<int>ve[N];
void dfs(int x){
	while(tot[x]<(int)ve[x].size()){
		int t=ve[x][tot[x]];
		if(!vis[t]){
			if(!bl[t]){
				tot[x]++; ans+=t; bl[t]=x; break;
			}
			if(bl[t]>x){
				dfs(bl[t]);
				bl[t]=x;break;
			}
		}
		tot[x]++;
	}
	return;
}
signed main(){
	int n=read(),m=read();
	for(int i=1;i<=m;i++)f[i]=read();
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1;i<=n;i++){
		int h=read();
		for(int j=1;j<=h;j++)ve[read()].push_back(i);
	}
	for(int i=1;i<=m;i++){
		int k=0;
		for(;tot[i]<(int)ve[i].size()&&k<f[i];tot[i]++){
			int h=ve[i][tot[i]];
			if(!bl[h]){
				ans+=h;k++;bl[h]=i;
			}
		}
	}
	cout<<ans<<"\n";
	for(int i=1;i<n;i++){
		vis[a[i]]=1;
		if(bl[a[i]]){
			ans-=a[i];
			dfs(bl[a[i]]);
		}
		cout<<ans<<"\n";
	}
}

时间复杂度：$O(n\log_n+\sum{n_i})$

完结撒花！