题解 P3254 【圆桌问题】
philosopherchang
2018-12-15 20:53:44
我也来发贪心。
把桌子大小和队伍大小从大到小排个序，然后一个一个的坐座位，最后在按照队伍编号再排回来。证明的话有人说不会，其实很简单，队伍越大越不容易满足，所以我们先让它满足，一个桌子一次只安一个人，满人的话就跳过那张桌子往后排，如果说在排座次的过程中，一直有一个人（也可能是多个）没地坐，也就是说一直到最后一张桌子还是满人，那么就可以巧妙地输出0了。
然后就是，蒟蒻不会vector，所以这是一个不用vector的题解，比[沛霖](https://www.luogu.org/space/show?uid=48455)dalao的代码量大，但我感觉应该更容易懂。
然后上代码
```cpp
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,ll;
struct node{
int num,wei,xy[1001],hao;//xy是每个人做的桌子编号
}a[1501];//我发现按着题目开数组最后一个点RE了，所以就大了点。
struct edge{//这个真的不是建边，是想不出结构体名称了。
int num1,shu,wi;
}b[3001];
bool c[3001];//判断桌子是否坐满
int cmp(node x,node y)
{
return x.num>y.num;
}
int cmp2(edge x,edge y)
{
return x.num1>y.num1;
}
int cmp1(node x,node y)
{
return x.wei<y.wei;
}
void dfs()
{
for(int i=1;i<=m;i++)
{
int cnt=0;
for(int j=1;j<=n;j++)
{
if(j==n&&c[j]==1)//如果扫到最后一张桌子发现桌子还是满的，就输出0，在void里没法直接输出，只能限定义一个ll变量。
{
ll=1;
return ;
}
if(c[j]==0)
{
a[i].num--;//此队伍中还剩下的人数
cnt++;
a[i].xy[cnt]=b[j].wi;
b[j].shu++;
if(b[j].shu==b[j].num1)
{
c[j]=1;
}
}
if(a[i].num==0)
{
a[i].hao=cnt;//记录下a[i].xy的长度，因为原来定义的num已经被我们减去了。
break;
}
}
}
return ;
}
void print()
{
sort(a+1,a+m+1,cmp1);
cout<<1<<endl;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=a[i].hao;j++)
{
cout<<a[i].xy[j]<<" ";
}
cout<<endl;
}
}
int main()
{
cin>>m>>n;
for(int i=1;i<=m;i++)
{
cin>>a[i].num;
a[i].wei=i;//wei是队伍编号
}
for(int i=1;i<=n;i++)
{
cin>>b[i].num1;
b[i].wi=i;wi是桌子编号
}
sort(a+1,a+n+1,cmp);
sort(b+1,b+n+1,cmp2);
dfs();//实在想不出函数名了才起的dfs。
if(ll==1)
{
cout<<0;
return 0;
}
print();
return 0;
}
```