排座椅[NOIP2008 年普及组]的解决办法

解题思路：这道题一开始的想法可能是暴力枚举，通过每一次遍历横切一刀或者竖切一刀，然后根据每次切完后的剩余“交头接耳”同学组数来打擂台，直到找到最小的一组，然后输出相应的切法。但这个方法实在太过麻烦，因为切的刀数不一定，用循环来写也不方便，还要多出很多个数组来记录各个变化值。

所以这里建议逆向思维

剩余“交头接耳”同学组数越少等价于被切掉的“交头接耳”同学组数最多

因此这道题其实并不需要管中间的变化过程，重要的是结果。

如此一来就简单了，我们只要在输入完后对输入的数据进行处理，对在某一行/某一列上同时存在的“交头接耳”同学的数量进行统计，数量越多，那这一行/这一列切开的优先级越高，最后根据可支配的横排和竖排的通道数依次按优先级从高到低输出结果即可

注意事项:

1. 义愤填膺！！这个结果必须要把切断的行/列编号从小到大输出，题干给的要求也不明显，我找了一个下午也没发现错在哪里，始终只有18分，害得我花29块大洋开通尊贵vip去核对输出，气死俺了！（不过我也因此学到了qsort的使用方法，也算是有所收获嘿嘿！）

2. 存储输入的数组必须开得足够大，最好10000，他的测试数据很恐怖。

   
   

参考代码:

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include<stdlib.h>
int search(int* h, int len)           //用于在行/列数组中找到当前切一刀能拆散的最多数量的邻桌     
{
    int m = 0,n=0;
    for (int i = 0; i < len; i++)
    {
    if (h[i] > m)
    {
    m = h[i];
    n = i;
    }
    }
    h[n] = 0;
    return n;
}
int cmp(const void* a, const void* b) 
{
    return *(int*)a - *(int*)b;
}                                   //qsort的参数必备函数

int main()
{
    int c[10000], h[1000] = { 0 }, l[1000] = { 0 };
    int ansh[1000] = { 0 }, ansl[1000] = {0};
    int m, n, k1, l1, d, x=0;
    scanf("%d %d %d %d %d", &m, &n, &k1, &l1, &d);
    for (int i = 0; i < d; i++)
    {
    scanf("%d %d %d %d", &c[4 * i], &c[4 * i + 1], &c[4 * i + 2], &c[4 * i + 3]);
    }
    int len = 4*d;
    for (int i = 1; i < len-2; i += 4)             //注意i的起始值、终值和步长
    {
    if (c[i] == c[i + 2])                          //列相等，用行可以阻断
    {
    x = (c[i-1]<c[i + 1])?c[i-1]:c[i+1];
    h[x] += 1;                                     //装桶，在该行切一刀能拆散的邻桌+1
    }
    }
    for (int i = 0; i < len-2; i += 4)
    {
    if (c[i] == c[i + 2])                           //行相等，用列可以阻断
    {
    x = (c[i+1] < c[i + 3]) ? c[i+1] : c[i + 3];
    l[x] += 1;
    }
    }
    int p = 0,q=0;                                   //以下为输出处理
    while (k1 > 0)
    {

    ansh[p] = search(h, m);
    k1--;
    p++;
    }
    qsort(ansh, p, sizeof(int), cmp);
    for (int i = 0; i <p; i++)
    {
    printf("%d ", ansh[i]);
    }
    printf("\n");
    while (l1 > 0)
    {

    ansl[q] = search(l, n);
    l1--;
    q++;
    }
    qsort(ansl, q, sizeof(int), cmp);
    for (int i = 0; i < q; i++)
    {
    printf("%d ", ansl[i]);
    }
    return 0;
}