题解 P3254 【圆桌问题】
违规用户名cVn1I&r!
2018-03-27 13:32:07
圆桌问题，虽然在网络流24题里，可是并不需要跑网络流，只要贪心即可。
本人蒟蒻不会证明，证明略。。。。
对于这个题，只需要开二个结构体，一个存桌子的容量和当前已用空间，一个存单位人的数量与去向。
利用自带的sort将单位大小与桌子容量大小由大到小排序，因为越大的单位需要越多的桌子。
```cpp
#include<bits/stdc++.h>
using namespace std;
struct node{
int size;
int now;
int pre;//结构体储存排序前的位置，方便最后输出
}ta[1000];
struct edge{
int cap;
int go[5000];
int pre;//结构体储存排序前的位置，方便最后输出
}uni[300];
bool cmp1(node a,node b)
{
return a.size>b.size;
}
bool cmp2(edge a,edge b)
{
return a.cap>b.cap;//由大到小排大小，容量
}
bool cmp3(edge a,edge b)
{
return a.pre<b.pre;
}
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>uni[i].cap;
uni[i].pre=i;//记录位置
}
for(int i=1;i<=m;i++)
{
cin>>ta[i].size;
ta[i].pre=i;//记录位置
}
int k=1;
sort(uni+1,uni+n+1,cmp2);
sort(ta+1,ta+1+m,cmp1);//排序
for(int i=1;i<=n;i++)//循环单位
{
int l=0;//当前单位可以满足的人数
for(int j=1;l<uni[i].cap&&j<=m;j++)
{
if(ta[j].now==ta[j].size)
continue;//桌子满了就往后找有空的
uni[i].go[++l]=j;ta[j].now++;//记录去向，当前桌子坐的人数++
}
if(l<uni[i].cap)//如果无法满足单位，退出
{
cout<<0;return 0;
}
}
sort(uni+1,uni+n+1,cmp3);//以原先顺序排单位，方便输出
cout<<1<<endl;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=uni[i].cap;j++)
//从1-n输出单位去向
cout<<ta[uni[i].go[j]].pre<<" ";//输出桌子原先位置
cout<<endl;
}
}
```