HDU5806 NanoApe Loves Sequence Ⅱ
NanoApe Loves Sequence Ⅱ
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/131072 K (Java/Others)
Total Submission(s): 517 Accepted Submission(s): 250
In math class, NanoApe picked up sequences once again. He wrote down a sequence with n numbers and a number m on the paper.
Now he wants to know the number of continous subsequences of the sequence in such a manner that the k-th largest number in the subsequence is no less than m.
Note : The length of the subsequence must be no less than k.
In each test case, the first line of the input contains three integers n,m,k.
The second line of the input contains n integers A1,A2,...,An, denoting the elements of the sequence.
1≤T≤10, 2≤n≤200000, 1≤k≤n/2, 1≤m,Ai≤109
求有多少个区间,使得区间内的第k大的值>=m.
将不小于m的数看作1,剩下的数看作0,那么只要区间内1的个数不小于k则可行,枚举左端点,右端点可以通过two-pointer求出。
/* ***********************************************
Author :guanjun
Created Time :2016/8/7 10:02:54
File Name :hdu5806.cpp
************************************************ */
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <iomanip>
#include <list>
#include <deque>
#include <stack>
#define ull unsigned long long
#define ll long long
#define mod 90001
#define INF 0x3f3f3f3f
#define maxn 10010
#define cle(a) memset(a,0,sizeof(a))
const ull inf = 1LL << ;
const double eps=1e-;
using namespace std;
priority_queue<int,vector<int>,greater<int> >pq;
struct Node{
int x,y;
};
struct cmp{
bool operator()(Node a,Node b){
if(a.x==b.x) return a.y> b.y;
return a.x>b.x;
}
}; bool cmp(int a,int b){
return a>b;
}
int a[];
int sum[];
int n,m,k;
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
//freopen("out.txt","w",stdout);
int t;
cin>>t;
while(t--){
scanf("%d%d%d",&n,&m,&k);
int x;
sum[]=;
for(int i=;i<=n;i++){
scanf("%d",&x);
if(x>=m)a[i]=;
else a[i]=;
sum[i]=sum[i-]+a[i];
}
ll ans=;
int r=;
for(int l=;l<=n;l++){//枚举左端点
while(r<=n&&sum[r]-sum[l-]<k)r++;
if(r>n)break;
ans+=(n-r+);
}
printf("%lld\n",ans);
}
return ;
}
最新文章
- SqlServer 2008登录时报错
- mfc学习之路--如何删除通过控件新增的变量
- ExtJS 刷新后,默认选中刷新前最后一次选中的节点
- .Net 2.0自带的Json序列化、反序列化方法
- tomcat中jsp编译
- Palindrome Permutation II 解答
- Python新手学习基础之运算符——比较运算符
- linux上配置bochs,搭建基于X86架构操作系统的开发环境
- .net string类型集合转int集合
- [工作积累] shadow map问题汇总
- 嵌入式C语言常见的错误
- MySQL&#160;性能优化--优化数据库结构之优化数据类型
- 2018/04/14 理解oAuth2.0
- Java Selenium - 元素操作 (三)
- JS onclick事件获取空间value
- sqlite3 的insert记录项思路
- ubuntu(14.4) 安装phpmyadmin
- PLSQL_统计信息系列04_统计信息的锁定和删除
- Linux centos7 redis安装教程
- linux怎样使用top命令查看系统状态