畜栏保留问题(OpenJ_Bailian - 4144)题解

太过爱你忘了你带给我的痛 2022-12-28 07:26 71阅读 0赞

### 文章目录 ###

*  题目描述
 *   *  输入要求
     *  输出要求
     *  样例输入
     *  样例输出
 *  算法分析
 *   *  算法证明过程（来自算法基础与在线实践）
 *  解题标程
 *  错题总结

--------------------

# 题目描述 #

农场有N头牛，每头牛会在一个特定的时间区间\[A, B\]（包括A和B）在畜栏里挤奶，且一个畜栏里同时只能有一头牛在挤奶。现在农场主希望知道最少几个畜栏能满足上述要求，并要求给出每头牛被安排的方案。对于多种可行方案，主要输出一种即可。

## 输入要求 ##

输入的第一行包含一个整数N(1 ≤ N ≤ 50, 000)，表示有N牛头；接下来N行每行包含两个数，分别表示这头牛的挤奶时间\[Ai, Bi\](1 ≤ A≤ B ≤ 1, 000, 000)。

## 输出要求 ##

输出的第一行包含一个整数，表示最少需要的畜栏数；接下来N行，第i+1行描述了第i头牛所被分配的畜栏编号（从1开始）。

## 样例输入 ##

5
    1 10
    2 4
    3 6
    5 8
    4 7

## 样例输出 ##

4
    1
    2
    3
    2
    4

# 算法分析 #

*  1、将牛按照开始时间从小到大进行排序
 *  2、将畜栏按照结束时间从小到大排序
 *  3、**牛越早开始工作，最早结束工作越好**
 *  需要注意：
 *  （1）上一头牛的结束时间和下一头牛的开始时间不能相等，相等也不能工作
 *  （2）需要用优先队列去维护畜栏来寻找最小结束时间的畜栏才不会超时（1000ms）
 *  （3）牛的输入顺序和输出结果的畜栏选择顺序应该相同，即不能改变牛的顺序。

## 算法证明过程（来自算法基础与在线实践） ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70]

# 解题标程 #

#include <iostream>
    #include <algorithm>
    #include <queue>
    #include <vector>
    using namespace std;
    
    struct A
    {
        
        int s,e,mark;   //mark用于记录牛的顺序
        bool operator < (const A &a)const   //优先队列按照结束时间排序
        {
        
            return e>a.e;
        }
    }c[50001];  //牛
    priority_queue<A>q;
    
    bool rule1(struct A a,struct A b)
    {
        
        if(a.s==b.s)
            return a.e<b.e;
        else
            return a.s<b.s;
    }
    
    int ans[50005]; //牛所进畜栏的标号
    
    int main()
    {
        
        int n;
        int countl=0;   //记录畜栏个数
        
        cin >> n;
        
        for(int i=0;i<n;i++){
        
            cin >> c[i].s >> c[i].e;
            c[i].mark=i;    //给牛标顺序号
        }
        
        sort(c,c+n,rule1);
        
        for(int i=0;i<n;i++){
        
            if(q.size()&&q.top().e<c[i].s){
        
                ans[c[i].mark]=ans[q.top().mark];   //有畜栏可以使用那么后进入的牛的畜栏号与出队列的畜栏号相同
                q.push(c[i]);
                q.pop();
            }
            else{
        
                countl++;
                ans[c[i].mark]=countl;
                q.push(c[i]);
            }
        }
        
        cout << countl << endl;
        
        for(int i=0;i<n;i++)
            cout << ans[i] << endl;
        
        return 0;
    }

--------------------

# 错题总结 #

*  优先队列的自定义排序：

struct A
    {
        
        int s,e,mark;
        bool operator < (const A &a)const   //重载
        {
        
            return e>a.e;
        }
    }c[50001];

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70]: /images/20221120/1526eaeefd054468a2c1b6891325945b.png