JZOJ 1115. 排座椅(seat)

题目描述

输入

输出

样例输入

4 5 1 2 34 2 4 32 3 3 32 5 2 4

样例输出

22 4

提示

【输入输出样例解释】

上图中用符号*、※、+ 标出了3对会交头接耳的学生的位置，图中3条粗线的位置表示通道，图示的通道划分方案是唯一的最佳方案。

分析

这一道题基本掌握了这个技巧直接秒杀，根本不在话下

第一行的输入不用说了，但是在第2到d+1行有一个技巧

我们不需要直接把这个数据存入，因为题目所说他们必定相

挨在一起，此时，我们只需要使用变量ABCD存下，

然后判断：如果他们是一行的，分割列的价值就加上一

否则（他们是一列的） 那么分割这个空位的价值就加1

最后只要权值最大的K 位横向, L位竖向的排序输出就可以了

1. 记得，一定要排序输出，不然见十八代祖宗

代码

#include <cstdio>using namespace std;int m,n,k,l,d;int h[1010],line[1010]; // 权值圈bool vish[1010],visl[1010]; // 找前k,l位大的权值是需要的标记数组int t[1010],t2[1010];  // 使用桶排将数据排序输出int min(int a,int b){return a>b?b:a;}int main(){freopen("seat.in","r",stdin);freopen("seat.out","w",stdout);//m->h n->lscanf("%d%d%d%d%d",&m,&n,&k,&l,&d);for(int i = 1;i <= d;i++){int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);if(a == c) // 利用题目的性质 :  使用变量ABCD存下line[min(b,d)]++; // 果他们是一行的，分割列的价值就加上一else //否则（他们是一列的） 那么分割这个空位的价值就加1h[min(a,c)]++;}while(k--) // 找前k大的权值并把他们进行桶排{int maxx=0,index=0;for(int i = 1;i <= m;i++){if(vish[i]==0&&maxx<h[i]){maxx=h[i];index=i;}}vish[index]=true;if(!index) break;t[index]=1;}bool bflag = 0;for(int i = 1;i <= 1000;i++){if(t[i]){if(bflag) printf(" ");else bflag = 1;printf("%d",i);}}printf("\n");bflag = 0;while(l--)// 找前l大的权值并把他们进行桶排{int maxx=0,index=0;for(int i = 1;i <= n;i++){if(visl[i]==0&&maxx<line[i]){maxx=line[i];index=i;}}visl[index]=true;if(!index) break;t2[index]=1;}for(int i = 1;i <= 1000;i++){if(t2[i]){if(bflag) printf(" ");else bflag = 1;printf("%d",i);}}printf("\n");return 0;}

本人的代码显得有些累赘，有心人可以把他优化一下。QVQ