题目描述

blablabla

算法思想

主要的算法思想就是区间分组
其实做法很简单，但是难点就是第二步，输出每一个牛对应的牛栏编号！看起来很简单，思考起来还行，实践起来很难

pair类主要是存储的区间的左右端点和牛的编号，也就是他们的输入顺序，需要从1开始，需要给i+1.

对pair类的数组排序完成后，进行判断，需要小根堆的数据结构，存储的是每组区间右端点的最大值
此时还需要创建一个类，Stall,其中包含区间的右端点、当前的围栏编号，和围栏编号下可以对应的牛的编号，牛的编号采用list存储，可以随时添加元素，数组不可以

小根堆的数据类型不可以单单是int类型的，需要是Stall类型的，需要实时更新右端点、围栏编号、和对应的牛编号

代码

package tanxin;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

class Pairq implements Comparable<Pairq>{
    int x;
    int y;
    int num;
    public Pairq(int x, int y, int num) {
        super();
        this.x = x;
        this.y = y;
        this.num = num;
    }
    @Override
    public int compareTo(Pairq p) {
        // TODO Auto-generated method stub
        return this.x>p.x?1 : -1;
    }

}

class Stall{
    int r;
    ArrayList<Integer> alArrayList= new ArrayList<Integer>();
    //列表中存储的是当前牛栏编号可以允许牛在这里吃草的编号
    //也就是牛的编号
    //idx和alArrayList是一个一对多的关系

    int idx;
    //表示第 i 头牛被安排到的畜栏编号
    public Stall(int r, int id, int idx) {
        super();
        this.r = r;
        this.alArrayList.add(id);
        this.idx = idx;

    }

}



public class 畜栏预定 {

    public static void main(String[] args) throws NumberFormatException, IOException {
      BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
      int n=Integer.parseInt(bufferedReader.readLine());
      Pairq a[]=new Pairq[n];
      String p[];
      int x;
      int y;

      for(int i=0;i<n;i++){
         p=bufferedReader.readLine().split(" ");

         x=Integer.parseInt(p[0]);
         y=Integer.parseInt(p[1]);

         a[i]=new Pairq(x, y, i+1);

      }
      Arrays.sort(a);



     PriorityQueue<Stall> queue = new PriorityQueue<Stall>(n,new Comparator<Stall> () {

        @Override
        public int compare(Stall o1, Stall o2) {
            // TODO Auto-generated method stub
            return o1.r >o2.r?1:-1;
        }

    });

     for(int i=0;i<n;i++){
         if(queue.isEmpty() || queue.peek().r >=a[i].x){
             queue.offer(new Stall(a[i].y, a[i].num, queue.size()+1));
         }else {
            Stall stall1= queue.poll();
            stall1.alArrayList.add(a[i].num);
            stall1.r=a[i].y;

            queue.offer(stall1);

            //此时必须要用新弹出的这个Stall,不可以新建一个Stall.
            //因为此时需要更新的是这个组的区间的右端点，在list中新加入当前的牛的编号
            //围栏的编号不需要进行更改
            //如果新建一个Stall对象的对象的话，会导致列表之前的元素清空，长度变为1，但是实际上列表的商都是需要累计的


        }
     }

      System.out.println(queue.size());

      //将牛的编号和牛栏编号一一对应

      int res[]=new int [n+1];
      //res存储的数组就是每一个牛的编号对应的围栏的编号，
      //n+1的长度范围是因为数组下标需要从1开始

      while(!queue.isEmpty()){

          Stall stall = queue.poll();


          //小根堆的形式
          for(Integer k:stall.alArrayList){
              //k表示的是stall.alArraylist中的元素，列表中存储的是牛的编号

             // System.out.println(k+" k");

              res[k]=stall.idx;

              //把当前的牛栏的编号，赋值给每一个牛，k表示的就是牛的编号

              //令当前队列中list存储的牛的编号等于当前的牛栏编号
              //相当于一对多的形式
          }
      }

      /*for(int i=1;i<=n;i++){
          System.out.println(res[i]);
      }*/
}

}