题解：P7403 [BalticOI 2002 Day1] Tennis Club
de_mosyt
·
·
题解
思路
贪心题，调整法。
我们每次选 G_i 最大的人和剩下 G 最大的 G_i 个人交朋友即可。
可以通过调整法证明：
$d_2−1,d_3−1,···,d_{d_1+1}−1,···,d_n$ 有解，然后归纳即可证明做法的正确性。
对于有解的情况，由于题目数据很小，小于 $1000$，所以我们可以定义一个二维数组记录朋友的关系，最后遍历输出即可。
## code
```cpp
#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;
}
```