【贪心思想】【桶排序】

解题思路:

错误思路：

一开始呢拿到这个题目，没好好读题，就想着来一对我砍一刀，最后把记录的那些个行列给输出就好了。提交后喜提18分，其他都是运行超时，还是死性不改，想到有个bug，我要是重复记录一行不也输出了吗？想到这个，我又先用LinkedList接那些个行列（保证唯一性）然后转换成数组排序输出，喜提18分，报的错误是输出超限。分析后知道了原因，用Linkedlist没考虑K，L的限制。所以来一对砍一刀可以但是我就打通那么多的K，L我只能选择隔断交头接耳的同学最多的前K个行前L个列才对。这时候我才注意到题目中的“最佳，最优”等词，才明白啊,它想考我贪心！！

题目的精髓就是该怎么砍才能分开最多的交头接耳的同学，必须行只能砍K刀，列只能砍L刀

弃暗投明后的思路：

一：首先拿到一对对交头接耳的同学的坐标

观察后得出结论如果x相同，那就从列砍一刀，把他们隔开，列号就是y值较小的；如果y相同，那就从行砍一刀，把他们隔开，行号就是x值较小的

来一对同学对应的行/列来一刀，那么我用两个数组分别记录每一行每一列被砍多少刀呗，最后取被砍的的最多的K个行L个列

二：填充完两个数组后，遇到个问题，数组的下标就是对应的行列号，而值就是其被砍得刀数。我如果直接排序，那就丢失了它的行列，这是万万不可行的。我最后就要输出最理想K个行号和L个列好啊。

三： 我不但要把它们按大小排序，还要把它们的行列即下标也保留住。基于这个特点，我想到用hashmap键值对和桶排序，最后选择了桶排序，定义容量为M的M个行桶和容量为N的列桶，通过桶排序，行桶排K次，然后从上一步得到的行数组中得到最理想的那一行的下标并作为桶下标，同时将桶的值置1，表示此桶有意义；列桶同理。

四：最后如果桶里装的是1则将其下标输出

注意事项:

第三步时，每次桶排序，拿到值最大的行或列的下标后，记得将原行列数组中对应的位置值置0，不然会影响下次桶排序的结果。

参考代码:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Stack;

/**
 * @Author:杨雨彤
 * @date:2024/1/9 20:42
 */
public class daydayone {
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException {
        String []s=br.readLine().split(" ");
        int M=Integer.parseInt(s[0]);
        int N=Integer.parseInt(s[1]);
        int K=Integer.parseInt(s[2]);
        int L=Integer.parseInt(s[3]);
        int D=Integer.parseInt(s[4]);
        int [] rows=new int[M];
        int [] columns=new int[N];
        for (int i = 0; i <D ; i++) {
            String[]s2=br.readLine().split(" ");
            int x1=Integer.parseInt(s2[0]);
            int y1=Integer.parseInt(s2[1]);
            int x2=Integer.parseInt(s2[2]);
            int y2=Integer.parseInt(s2[3]);
            if(x1==x2){
                columns[Math.min(y1,y2)]+=1;
            }else{
                rows[Math.min(x1,x2)]+=1;
            }
        }
        int []cntR=new int[M];
        int []cntC=new int[N];
        //用cntR记录K行,记录能隔开最多对同学的前K个最适合的行
        for (int i = 0; i <K ; i++) {//只取K行
            int max=-1;//记录每次遍历中最大的那个数
            int index=-1;//记录最大数的下标即行数
            for (int j = 0; j < rows.length ; j++) {
                if(rows[j]>max){
                    max=rows[j];
                    index=j;
                }
            }
            rows[index]=0;//置0,不影响下次桶排序
            cntR[index]=1;//置1表示此桶有效,下标就是行号
        }
        //用cntC记录L列,记录能隔开最多对同学的前L个最适合的列
        for (int i = 0; i <L ; i++) {//只取L列
            int max=-1;//记录每次遍历中最大的那个数
            int index=-1;//记录最大数的下标即列号
            for (int j = 0; j < columns.length ; j++) {
                if(columns[j]>max){
                    max=columns[j];
                    index=j;
                }
            }
            columns[index]=0;//置0,不影响下次桶排序,找下个最理想列
            cntC[index]=1;//置1表示此桶有效,下标就是列号
        }
        int count1=0;
        for (int i = 0; i < cntR.length ; i++) {
            if(cntR[i]!=0&&count1<K){
                System.out.print(i+" ");
                ++count1;
            }else if(cntR[i]!=0&&count1==K){
                System.out.print(i);
            }
        }
        System.out.println();
        int count2=0;
        for (int i = 0; i < cntC.length ; i++) {
            if(cntC[i]!=0&&count2<L){
                System.out.print(i+" ");
                ++count2;
            }else if(cntC[i]!=0&&count2==L){
                System.out.print(i);
            }
        }
    }
}