题目链接

因为题目说输入保证会交头接耳的同学前后相邻或者左右相邻,所以一对同学要分开有且只有一条唯一的通道才能把他们分开。

于是可以吧这条通道累加到一个数组里面。应为题目要求纵列的通道和横列的通道条数有限制,所以我们用贪心,将数据存入结构体在根据每一条线隔开的同学对数排序,得出前k条横线和前l条纵线就是要分割的通道。

因为题目要求输出按照$a_i<a_{i+1}$,$b_i<b_{i+1}$。
所以我们在根据$a_i$和$b_i$从小到大排序。

上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
using namespace std;
int n,m,k,l,o;
int a,b,c,d;
int ks[2009],ls[2009];
struct aa{
int u,s;
}ans[2009];
int lans;
int u,mx;
bool pp(aa x,aa y)
{
return x.s>y.s;
}
bool pp1(aa x,aa y)
{
return x.u<y.u;
}
int main()
{
scanf("%d%d%d%d%d",&n,&m,&k,&l,&o);
for(int j=1;j<=o;j++)
{
scanf("%d%d%d%d",&a,&b,&c,&d);
if(a>c || b>d)
{
int t;
t=a;a=c;c=t;
t=b;b=d;d=t;
}
if(c==a+1) ks[a]++;
if(d==b+1) ls[b]++;
}
for(int j=1;j<n;j++)
{
if(ks[j]>0)
{
lans++;
ans[lans].u=j;
ans[lans].s=ks[j];
}
}
sort(ans+1,ans+lans+1,pp);
sort(ans+1,ans+k+1,pp1);
for(int j=1;j<=k;j++)
printf("%d ",ans[j].u);
lans=0;
for(int j=1;j<m;j++)
{
if(ls[j]>0)
{
lans++;
ans[lans].u=j;
ans[lans].s=ls[j];
}
}
puts("");
sort(ans+1,ans+lans+1,pp);
sort(ans+1,ans+l+1,pp1);
for(int j=1;j<=l;j++)
printf("%d ",ans[j].u);
return 0;
}

最后更新: 2018年10月07日 14:00

原始链接: http://oierlin.cf/2018/09/02/【洛谷】P1056【排座椅】/

× 请我吃糖~
打赏二维码