自动搬运

查看原文

来自洛谷，原作者为

	Light_az florr.io 同名 || 莱特阿哲

搬运于2025-08-24 21:45:20，当前版本为作者最后更新于2023-03-26 09:48:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

详细图解和样例讲解

这道题目难度评的有点高，应该是一道绿色题目。本题难度可能在于题意不容易理解，题目大概意思是一共有 $n + 1$ 个点，其中有一个点是多余的，问你那些点有可能是多余的。

忽略第一行，其中在第 $1$ 到 $n+1$ 行中 ，$a_i$ 代表编号为 $i$ 的点链接了多少条边，为什么会有多余的点呢？首先我们来分析一下样例：

• 当 $1$ 号点多余时，这张图是长这样子的：

• 当 $4$ 号点多余时，这张图是长这样子的：

• 当 $5$ 号点多余时，这张图是长这样子的：

• 当其它点多余时，无法组成一个图。

发现了吗 ？我们只需要用 $O(n+1)$ 的时间去枚举哪一个点不合法，然后再判断剩下的点构成的图是否合法即可。接下来，我们将问题转化成 $n$ 个点是否可以构成一张图，我们可以采用排序加模拟的方式，下面会演示一遍完整流程：

• 当 $1$ 号点是多余的，即使用 $2$ 到 $5$ 号点构图时：

先进行边数排序，发现 $5$ 号点连接了 $3$ 条边，是最多的，因此我们先连接它：

连接之后 $5$ 号点已经连接完了， $1,2,3$ 号各减少一条边。

我们再次进行排序，发现 $2$ 号点连接了 $1$ 条边，是最多的，因此我们连接它：

连接之后 $1,2,3$ 号点已经连接完了，发现没有剩余边数，因此方案成立。

以此类推，我们可以求出其他方案是否合法，但是在判断过程中我们要注意：

• 保证连接的点还有剩余边数允许连接，我们不能连接一个边数为 $0$ 的点。

• 在特殊情况下，快速排序会退化成线性复杂度，因此我们可以使用归并排序。

最后，就是完整的代码实现了：

#include<bits/stdc++.h>
#define ll long long
#define F(i,j,n) for(int i=j;i<=n;i++)
#define Tr(v,e) for(int v:e)
#define D double
#define ps push_back
#define Test ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
using namespace std;
const int N=1e6+10,NN=1e4+10;
ll n,m,k,x,y,u,v,w,cnt=0,t=0,l,r,len,T;
ll mini=INT_MAX,maxi=0,Mod;
string s1,s2;
ll a[N],b[N],ans[N];
void copy(ll id){
	ll t=0;
	F(i,1,n+1){
		if(i==id) continue;//去掉 i 点
		b[++t]=a[i];
	}
}
bool cmp(ll a,ll b){
	return a>b;
}
void print(){
	F(i,1,n) cout<<b[i]<<" ";
	cout<<"\n";
}
ll check(){
	ll k=n;
	stable_sort(b+1,b+1+n,cmp);//归并排序
	while(k){
		ll id=2;//从第 2 小的开始
		while(b[1]&&b[id]) b[1]--,b[id]--,id++;//两个点都有剩余的边允许连接，双方边数减少，进行下一条边
		if(b[1]) return 1;//有剩余边，不合法
		stable_sort(b+1,b+1+k,cmp);//归并排序
		k--;//有一个元素值变成 0，可以省略它的排序
	}
	return 0;//合法
}
int main(){
    Test;//输入优化
	cin>>n;
	F(i,1,n+1) cin>>a[i];
	F(i,1,n+1){
		copy(i);//枚举没有 i 点的情况
		if(!check()) cnt++,ans[++t]=i;//不合法情况多了一种
	}
	cout<<cnt<<"\n";
	F(i,1,cnt) cout<<ans[i]<<"\n";
	return 0;
}