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

Minary_Acdream

http://f10.moe/

 
 
 

日志

 
 

[nbut] 1147 Bad O2Jam  

2012-11-08 22:25:37|  分类: NBUT OJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
这题就可以说是上面一题 [1060 Countless Core Computers] 的升级版,也是求在某个时间内的最大任务数(这里是面条数)。
升级的地方在于 每秒能按住的面条数有限制。
题目链接
样例分析
样例输入
3 2 1 //3是面条数,2是问题数,1是每次能按住的面条数
0 5 //第1条面条的时间段为0~5
6 7           //第2条面条的时间段为6~7
1 3 //第3条面条的时间段为1~3
2 //问题
//问题
样例输出
1
0
3

代码如下:


#include<iostream>
#include<algorithm>
using namespace std;
#define Max 10000000

int core[Max];
int st[300001],et[300001];

int main()
{
int n,q,k;
while(~scanf("%d%d%d",&n,&q,&k))
{
for(int i = 0;i < n;i ++)
{
scanf("%d%d",st + i,et + i);
et[i] ++;
}
sort(st,st + n);
sort(et,et + n);
int MaxT = et[n - 1];
int ti = 0, tj = 0;
memset(core,0,sizeof(core));
for(int i = 0;i <= MaxT;i ++)
{
if(i != 0) core[i] = core[i - 1];
while(ti < n && st[ti] == i)
{
core[i] ++;
ti ++;
}
while(tj < n && et[tj] == i)
{
core[i] --;
tj ++;
}
}
while(q--)
{
int Q;
scanf("%d",&Q);
if(core[Q] - k >= 0)
printf("%d\n",core[Q] - k);
else printf("0\n");
}
int num = 0;
for(int i = 0;i <= MaxT;i ++)
{
if(core[i] - k >= 1) num ++;
}
printf("%d\n",num);
}
return 0;
}



/*
样例输入
3 2 1
0 5
6 7
1 3
2
5
样例输出
1
0
3*/



  评论这张
 
阅读(111)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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