CSU oj 1685 Entertainment Box

逃离我推掉我的手 2022-08-21 12:44 130阅读 0赞

题目链接：[http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1685][http_acm.csu.edu.cn_OnlineJudge_problem.php_id_1685]

题目大意：有k个磁道，每个磁道可以记录节目，给出k个节目的开始和结束时间，问最多能记录多少个节目。  
如有2个磁道  
4个节目  
时间为 1 3  
2 4  
3 5  
4 6  
则四个节目都记录  
第一个磁道记录 1 3 3 5  
第二个磁道记录 2 4 4 6

解题思路：先按结束时间排序，然后依次找出  
在磁道中的节目的结束时间  
离下一个节目开始时间  
差最小的磁道中的节目节目  
这个磁道中的节目将被替换  
按照这个思路排节目就好了

#include <vector>
    #include <list>
    #include <map>
    #include <set>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <bitset>
    #include <algorithm>
    #include <functional>
    #include <numeric>
    #include <utility>
    #include <sstream>
    #include <iostream>
    #include <iomanip>
    #include <cstdio>
    #include <cmath>
    #include <cstdlib>
    #include <cstring>
    #include <ctime>
    #include <cassert>
    #define RI(N) scanf("%d",&(N))
    #define RII(N,M) scanf("%d %d",&(N),&(M))
    #define RIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
    #define Cl0(a) memset((a),0,sizeof(a))
    using namespace std;
    const int inf=1e9;
    const int inf1=-1*1e9;
    typedef long long LL;
    
    multiset<int> mset;
    int ans=0;
    struct t
    {
        int st,en;
    } time1[100005];
    
    bool cmp(t a,t b)
    {
        return a.en<b.en;
    }
    int main()
    {
        int n,k;
        RII(n,k);
        for(int i=0; i<n; i++)
        {
            RII(time1[i].st,time1[i].en);
        }
        sort(time1,time1+n,cmp);
        int k1=0;
        for(int i=0; i<k; i++)
            mset.insert(0);
        for(int i=0; i<n; i++)
        {
            multiset<int>::iterator it=mset.upper_bound(time1[i].st);
            if(it!=mset.begin())
            {
                mset.erase(--it);
                mset.insert(time1[i].en);
                ans++;
            }
        }
    
        cout<<ans<<endl;
        return 0;
    }

[http_acm.csu.edu.cn_OnlineJudge_problem.php_id_1685]: http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1685