P3104题解

· · 题解

详细图解和样例讲解

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

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

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

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

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

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

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

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

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

#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;
}