洛谷P1056 排座椅

淡淡的烟草味﹌ 2022-04-14 06:57 84阅读 0赞

#### 先上题目链接 ####

[https://www.luogu.org/problemnew/show/P1056][https_www.luogu.org_problemnew_show_P1056]

注释写得多，直接贴代码了：

#include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    int main() { 
    	int m, n, k, l, d,i,j,max;
    	short int ax, ay, bx, by;
    
    	cin >> m >> n >> k >> l >> d;
    	short int *horizontal= new short int[m]();  //用数组存储第i根横/竖线能分割的同学数量
    	short int *vertical = new short int[n]();
    	bool *nx = new bool[m];
    	bool *ny = new bool[n];
    	fill(nx, nx + m, false);
    	fill(ny, ny + n, false);
    
    	for (i = 0; i < d; i++) { 
    		cin >> ax >> ay >> bx >> by;              //注意这里的x和y指的是行和列，不是横坐标与纵坐标
    		if (ax == bx) {                    //同一行，用竖线分开
    			vertical[ay > by ? by : ay]++;
    		}
    		else if (ay == by) { 
    			horizontal[ax > bx ? bx : ax]++;
    		}
    	}
    
    	for (i = 1; i <= k; i++) {  //每次找出当前可以分割最多对交头接耳同学的那根线的下标，在标记用的数组中令其对应的位置为1,这样做既可以从所有能分割同学的线中找出分割同学最多的k条线，还为后面的要求：结果按下标顺序输出 做了准备
    		max = -1;
    		int tmp;
    		for (j = 1; j < m; j++) {           //这层循环用来找此轮中分割交头接耳同学数最多的那一条横线的下标（tmp）
    			if (horizontal[j] > max) { 
    				max = horizontal[j];
    				tmp = j;
    			}
    		}//退出这个循环时p为分割最大的线的下标
    		horizontal[tmp] = false;//求出一条分割最多的线后，把这条线的数据清空，进行下一轮的排序 
    		nx[tmp]=true;
    	}
    	for (i = 1; i <= l; i++) {              //竖线同理
    		max = -1;
    		int tmp;
    		for (j = 1; j < n; j++) { 
    			if (vertical[j] > max) { 
    				max = vertical[j];
    				tmp = j;
    			}
    		}
    		vertical[tmp] = false;
    		ny[tmp]=true;
    	}
    
    	for (i = 0; i < m; i++) { 
    		if (nx[i]) {        //有标记则说明这行需要分割
    			cout << i << ' ';
    		}
    	}
    	cout << endl;
    	for (i = 0; i < n; i++) { 
    		if (ny[i]) { 
    			cout << i << ' ';
    		}
    	}
    
    	delete[]horizontal;
    	delete[]vertical;
    }

### 学到的： ###

**1.**  
关于动态数组初始化的内容：  
对于内置数据类型元素的数组，必须使用()来显示指定程序执行初始化操作，否则程序不执行初始化操作：

int \*pia = new int\[10\]; // 每个元素都没有初始化

int \*pia2 = new int\[10\] (); // 每个元素初始化为0

类类型元素的数组，则无论是否使用（），都会自动调用其默认构造函数来初始化：

string \*psa = new string\[10\]; // 每个元素调用默认构造函数初始化

string \*psa = new string10; // 每个元素调用默认构造函数初始化

**2.**  
桶排序的基本思想（与这题的horizontal和vertical数组的使用有相通之处）

\*\*3 \*\* 注意一种错误：监视界面查看bool类型的值为"true(205)",这个真值的实际数字就是205，用它与true比较会得出不相等的结论。出现该错误的原因可能是bool值未声明就被拿来使用。

[https_www.luogu.org_problemnew_show_P1056]: https://www.luogu.org/problemnew/show/P1056