自动搬运

查看原文

来自洛谷，原作者为

	floris 浸入我们残缺的时光

搬运于2025-08-24 22:29:30，当前版本为作者最后更新于2025-01-15 21:39:01，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

思路

贪心题，调整法。

我们每次选 $G_i$ 最大的人和剩下 $G$ 最大的 $G_i$ 个人交朋友即可。

可以通过调整法证明：

$d_1⩾d_2⩾···⩾d_n$ 有解等价于 $d_2−1,d_3−1,···,d_{d_1+1}−1,···,d_n$ 有解，然后归纳即可证明做法的正确性。

对于有解的情况，由于题目数据很小，小于 $1000$，所以我们可以定义一个二维数组记录朋友的关系，最后遍历输出即可。

code

#include<bits/stdc++.h>
using namespace std;
#define N 1005
int n,a[N];
bool f[N][N];
struct node{
    int c,id;
}e[N];
bool cmp(node x,node y){
    return x.c>y.c;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
	cin>>n;
    for(int i=1;i<=n;i++){
        cin>>e[i].c;
        e[i].id=i;
    }
    sort(e+1,e+n+1,cmp);
    for(int i=1;i<=n;i++){
        sort(e+1,e+n+1,cmp);
        if(e[1].c==0) break;
        for(int j=2;j<=e[1].c+1;j++){
            if(e[j].c==0){
                cout<<"NO SOLUTION"<<'\n';
                return 0;
            }
            e[j].c--;
            f[e[1].id][e[j].id]=1;
            f[e[j].id][e[1].id]=1;
        }
        e[1].c=0;
    }
    cout<<"SOLUTION"<<'\n';
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(f[i][j]==1) cout<<j<<" ";
        }
        cout<<'\n';
    }
	return 0;
}