注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

aspe的博客

OI之路阻且长

 
 
 

日志

 
 

超级教室  

2015-05-21 20:02:06|  分类: 解题报告 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
解法一:
解法二:
解法三:
解法四:用前缀和的思路,时间复杂度为O(nlog2n){排序}。

超级教室 - 杨鸿飞 - 一个叫杨鸿飞的人的博客
 

#include<iostream>
#include<fstream>
#include<algorithm>

using namespace std;

struct Tclass
{
int a=0,b=0; 
};

Tclass a[10000];
int len;

bool _cmp(Tclass x,Tclass y)
{
if (x.a==y.a) return x.b>y.b;   //先加后减,因为在一节课下课时,另一节课刚好上课,有多一个课室
return x.a<y.a;
}

int main()
{
    int len=0,n,sum=0,max=0,i;
    cin>>n;
    for (i=0; i<n; i++)
    {
        len++; cin>>a[len-1].a; a[len-1].b=1;      //b点记录是开始还是结束,1开始,-1结束
        len++; cin>>a[len-1].a; a[len-1].b=-1;    //a点记录时间点
    }
        sort(a+0,a+len,_cmp);   //排序时间点
        for (i=0; i<len; i++)
    {
        sum+=a[i].b;     //记录前缀和,每一次为当前时间点课室数,为1就多一节课,为2就少一节课
        if (sum>max) max=sum;     //选出最多课室数
    }
    cout<<max;
}
  评论这张
 
阅读(15)| 评论(1)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018