本文共 1314 字，大约阅读时间需要 4 分钟。

C. 【例题3】畜栏预定

内存限制：256 MiB 时间限制：1000 ms 标准输入输出 题目类型：传统 评测方式：Special Judge

题目描述

有 n 头牛在畜栏中吃草。每个畜栏在同一时间段只能提供给一头牛吃草，所以可能会需要多个畜栏，给出第 i 头牛开始吃草的时间区间$[a_i,b_i]$ ，求需要的最少畜栏数和每头牛对应的畜栏方案。

输入格式

第一行一个正整数 n。

接下来 n 行，第 i 行两个正整数 $a_i,b_i$。

输出格式

第一行一个整数n，表示需要的最少畜栏数。

接下来 n 行，第 i 行一个整数表示第 i 头牛的对应畜栏，编号是从 1 开始的连续整数，方案合法即可。

样例

样例输入

51 102 43 65 84 7

样例输出

412324

数据范围与提示

对于 $\%100$ 的数据，有$1\le N\le 5\times 10^4,1\le a_i,b_i\le 10^6$。

题解

牛按$a_i$排序，再依次枚举，

对于每一头牛，若当前没有可用畜栏，则新加一个畜栏； 若有，则用，并维护这个畜栏的牛吃草的结束时间。 可用小根堆来找出吃草结束时间最早的畜栏， 于是时间复杂度可优化成$O(n\log n)$

代码

#include
   
    #include
    
     #include
     
      #include
      
       #define ll long longusing namespace std;ll n,ans[100001];struct que{
   	ll r;	ll id;	bool operator < (const que &a) const	{
   		return r>a.r;	}};priority_queue 
       
         q;struct node{
   	int l,r,id;} a[100001];ll cmp(node x,node y){
   	return x.l
        
         >n; for(int i=1; i<=n; i++) { cin>>a[i].l>>a[i].r; a[i].id=i; } sort(a,a+n+1,cmp); for(int i=1; i<=n; i++) { if(!q.size()||q.top().r>=a[i].l)//若没有可用畜栏，新加畜栏 { ans[a[i].id]=q.size()+1; q.push((que){ a[i].r,q.size()+1}); } else { ans[a[i].id]=q.top().id; q.pop(); q.push((que){ a[i].r,ans[a[i].id]}); } } cout<
         
          <
         
        
       
      
     
    
   

转载地址：http://ohpwb.baihongyu.com/