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

aspe的博客

OI之路阻且长

 
 
 

日志

 
 

bestcoder0806_T3  

2016-08-13 07:46:29|  分类: 解题报告 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
问题描述
退役狗 NanoApe 滚回去学文化课啦!

在数学课上,NanoApe 心痒痒又玩起了数列。他在纸上随便写了一个长度为n的数列,他又根据心情写下了一个数m。

他想知道这个数列中有多少个区间里的第k大的数不小于m,当然首先这个区间必须至少要有k个数啦。

1≤T≤10, 2≤n≤200000, 1≤k≤n/2, 1≤m,A?i≤10^9
??
题目链接:http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=721&pid=1003
======================================
        蛤?区间第k大?这这这不是什么高级的东西吗?
        其实,是你想多了,这就是一道简单的单调队列的题目,如果f[i~j]的第k大不小于m,那么f[i~j+1],f[i~j+2],……,f[i~n]的第k大也必定会不小于m,这是很显然意见的。那么用单调队列找一个最小的j就可以了。
        还有一种高级的数学做法,我也不怎么会……
======================================

#include <algorithm>
#include <iostream>
#include <cstdio>

using namespace std;

int a[200010];

int main()
{
int t; scanf("%d",&t);

for ( ; t>0; t--)
{
int n,k,m; scanf("%d%d%d",&n,&m,&k);

for (int i=0; i<n; i++) scanf("%d",&a[i]);

long long ans=0;

int sm=0,j=0;

for (int i=0; i<n; i++)
{
for ( ; j<n && sm<k; j++)
if (a[j]>=m) sm++; //大于m的有几个

//cout<<j<<endl;

if (sm>=k) ans+=n-j+1;

if (a[i]>=m) sm--; //滚动
}

cout<<ans<<endl;
}
}


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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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