排座椅

#include <stdio.h>
#include <stdlib.h>
//既然是贪心，那就找每一列和每一行的交头接耳的有多少对。优先选，某一行或者某一列交头接耳人数最多的给干掉就可以了，实现所谓的贪心。直到用完所有通道，好像也还行
//大佬的思路看来跟你想的一样

typedef struct
{
    int pos; //某一行或者某一列
    int count;  //记录这一行或者这一列上有多少对交投杰尔的同学
} hang_lie;

int compare(const void *p1,const void *p2)
{
    //如果相同应该按序号升序
    hang_lie temp1=(*(hang_lie*)p1);
    hang_lie temp2=(*(hang_lie*)p2);

    if(temp1.count<temp2.count)
    {
        return 1;
    }else if (temp1.count>temp2.count) {
        return -1;
    }else {
        //如果相同应该按序号升序
        if(temp1.pos<temp2.pos)
        {
            return -1;
        }else {
            return 1;
        }
    }

    return 0;//降序
}

int compare2(const void *p1,const void *p2)
{
    return (*(hang_lie*)p1).pos-(*(hang_lie*)p2).pos;//序号升序
}

int main() {

    int n, m,k,l,d;  //k行，l列
    scanf("%d %d %d %d %d",&n,&m,&k,&l,&d);
    
    //创建两个数组分别记录每行每列上有多少对交投杰尔的同学
    hang_lie* hang=malloc(sizeof(hang_lie)*n); //创建n行
    hang_lie* lie=malloc(sizeof(hang_lie)*m); //创建m列
    
    for (int i=0; i<n; i++) {  //初始化数值
        hang[i].pos=i+1;
        hang[i].count=0;
    }
    for (int i=0; i<m; i++) {
        lie[i].pos=i+1;
        lie[i].count=0;
    }

    //开始记录每行每列有多少对交头接耳同学
    for (int i=0; i<d; i++) {
        int x,y,p,q; 
        scanf("%d %d %d %d",&x,&y,&p,&q);

        //根据位置判断这两个同学是在行上还是列上交投接耳
        if (x==p) {   //如果纵坐标相同说明在行上交头
            lie[y<q?y-1:q-1].count++;//在这个列上记录一对 ,搞错了应该是用用小的那个列作为下标，而不是用x
        }else if (y==q){
            hang[x<p?x-1:p-1].count++;//在这个行上记录一对,应该是用小的另一个坐标那个作为下标
        }
    }

    //查看统计结果
    // printf("hang:\n");
    // for (int i=0; i<n; i++) {  //初始化数值
    //     printf("%d=%d \n",hang[i].pos,hang[i].count);
    // }
    // printf("列:\n");
    // for (int i=0; i<m; i++) {
    //     printf("%d=%d \n",lie[i].pos,lie[i].count);
    // }

    //排序后选最大的分割
    qsort(hang, n, sizeof(hang_lie), compare);
    qsort(lie, m, sizeof(hang_lie), compare);
    
    //行选前k个，列选前L个进行分割即可
    //还得按序号排序一次
    qsort(hang, k, sizeof(hang_lie), compare2);  //注意用的是compare2的排序
    qsort(lie, l, sizeof(hang_lie), compare2);
    
    for (int i=0; i<k; i++) {  //行选前k个，列选前L个输出即可
        printf("%d ",hang[i].pos);
    }
    printf("\n");
    for (int i=0; i<l; i++) {  //行选前k个，列选前L个输出即可
        printf("%d ",lie[i].pos);
    }

    return 0;
}