HDU 6231 (二分+双指针)
2024-08-23 06:49:51
题意:给一个长度为n的数组,问在由这个数组的所有的区间第k小组成B数组中,第m大元素是多少
解法:这题较难的地方在于转化思维。如果去求所有区间的第k小,最坏复杂度是O(n*n)肯定超时。
这题正确的解法是二分一个最大的x,这个x满足有大于等于m个【区间的第k小】大于等于x.。
所以关键在于,如何求有多少个区间的第k小大于等于x.
一个区间第k小要大于等于x,则这个区间至少要有k个数大于等于x..
我们枚举区间的左端点L。对于每个左端L,可以找一个最小的r使得,当右端点大于等于r时,[L,r]有k个数大于等于x。所以L为左端点的区间中满足要求的区间数有 n-r+1个
而这个r关于l显然是有单调性的,所以可以考虑用双指针O(n)求出所有r.。
所以算法复杂度O(nlogn)
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<algorithm>
#include<vector>
#include<set>
#define ll long long
using namespace std;
int a[],b[];
long long num;
int check(int n,int k,int m)
{
long long sum=;
int i,j=,s=;
for(i=;i<=n;i++)
{
while(s<k&&j<=n)
{
j++;
if(a[j]>=m)
s++;
}
if(j>n)
break;
sum+=n-j+;
if(a[i]>=m)
s--;
}
// printf("%d %d\n",m,sum);
return sum<num;
}
void find(int n,int k)
{
int l=,r=n+,m;
while(l+<r)
{
m=(l+r)/;
if(check(n,k,b[m]))
r=m;
else
l=m;
}
printf("%d\n",b[l]);
}
int main()
{
int i,j,n,t,m,k,l,r;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%I64d",&n,&k,&num);
for(i=;i<=n;i++)
{
scanf("%d",&a[i]);
b[i]=a[i];
}
sort(b+,b+n+);
find(n,k);
}
return ;
}
Ac代码
最新文章
- 搞不清FastCgi与PHP-fpm之间是个什么样的关系?
- .net程序部署(mono方式)
- Python Day6
- .Net简单图片系统-本地存储和分布式存储
- Java垃圾收集算法介绍
- QUICK START GUIDE
- 文字编辑器kindeditor-min.js的使用
- 01scala环境搭建和基础
- 基于OpenDaylight和Mininet的试验床平台搭建
- centos rsync安装配置
- Csharp volatile 关键字
- Java基础知识强化之IO流笔记58:内存操作流
- mysql设置连接等待时间(wait_timeout)
- 从源代码分析modelDriven拦截器和params拦截器和拦截器prepare 和paramsPrepareParamsStack拦截器栈(让你的Struts2代码更简洁——如何培养框架设计能力
- AspNetPager常用属性及一些样式
- [Mark] openvswitch megaflow
- NSTimer内存方面的探究
- 主线程中也不绝对安全的 UI 操作
- 安卓笔记-- popupwindow back键不消失的问题
- JAVA堆栈的区别
热门文章
- 01_9_Struts用ModelDriven接收参数
- ios sinaweibo 客户端(三)
- JS数据结构与算法--单向链表
- cppoop作业:Inheritance+Composition 關係下的構造和析構
- ubuntu 设置定时任务
- Linux下的硬件驱动——USB设备(转载)
- stm32L0工程建立(HAL+IAR,无cubemx)
- $ cat /usr/share/doc/wireshark-common/README.Debian
- Linux学习-循环执行的例行性工作排程
- hdu4861 我只能说这是找规律=.=