# 洛谷P1056 排座椅

## 题目描述

### 输入输出样例

```4 5 1 2 3
4 2 4 3
2 3 3 3
2 5 2 4
```

```2
2 4
```

2008年普及组第二题

## Solution

### 存储结构

```cin>>m>>n>>k>>l>>d;
int x1,y1,x2,y2;
for(int i=1;i<=n;i++) hen[i].hs=i;
for(int i=1;i<=m;i++) shu[i].hs=i;
for(int i=1;i<=d;i++)
{
cin>>x1>>y1>>x2>>y2;
if(x1==x2)
{
hen[min(y1,y2)].num++;
}
if(y1==y2)
{
shu[min(x1,x2)].num++;
}
}```

### 排序1

```sort(shu+1,shu+m+1,cmp);
sort(hen+1,hen+n+1,cmp);```

cmp

`bool cmp(aisle ta,aisle tb){return ta.num>tb.num;}`

### 排序2

“没有一遍sort解决不了的事。如果有，就再来一遍sort！”

```sort(shu+1,shu+k+1,cmp2);
sort(hen+1,hen+l+1,cmp2);
for(int i=1;i<=k;i++)
{
cout<<shu[i].hs;
if(i!=k) cout<<" ";
}
cout<<endl;
for(int i=1;i<=l;i++)
{
cout<<hen[i].hs;
if(i!=l) cout<<" ";
}```

cmp2

`bool cmp2(aisle ta,aisle tb){return ta.hs<tb.hs;}`

## 完整代码

``` 1 #include<bits/stdc++.h>
2 using namespace std;
3 struct aisle{
4     int hs;
5     int num;
6 }hen[10001],shu[10001],ansa[10001],ansb[10001];
7 bool cmp(aisle ta,aisle tb){return ta.num>tb.num;}
8 bool cmp2(aisle ta,aisle tb){return ta.hs<tb.hs;}
9 int m,n,k,l,d,h,s;
10 int main()
11 {
12 //    freopen("1056text.txt","r",stdin);
13     cin>>m>>n>>k>>l>>d;
14     int x1,y1,x2,y2;
15     for(int i=1;i<=n;i++) hen[i].hs=i;
16     for(int i=1;i<=m;i++) shu[i].hs=i;
17     for(int i=1;i<=d;i++)
18     {
19         cin>>x1>>y1>>x2>>y2;
20         //hen
21         if(x1==x2)
22         {
23             hen[min(y1,y2)].num++;
24         }
25         if(y1==y2)
26         {
27             shu[min(x1,x2)].num++;
28         }
29     }
30     sort(shu+1,shu+m+1,cmp);
31     sort(hen+1,hen+n+1,cmp);
32     sort(shu+1,shu+k+1,cmp2);
33     sort(hen+1,hen+l+1,cmp2);
34     for(int i=1;i<=k;i++)
35     {
36         cout<<shu[i].hs;
37         if(i!=k) cout<<" ";
38     }
39     cout<<endl;
40     for(int i=1;i<=l;i++)
41     {
42         cout<<hen[i].hs;
43         if(i!=l) cout<<" ";
44     }
45     return 0;
46 }```

End

(0)
(0)