hdu 6231 -- K-th Number(二分+尺取)
2018-06-17 21:34:49来源:未知 阅读 ()
题目链接
Now Alice want to build an array B by a parameter K as following rules:
Initially, the array B is empty. Consider each interval in array A. If the length of this interval is less than K, then ignore this interval. Otherwise, find the K-th largest number in this interval and add this number into array B.
In fact Alice doesn't care each element in the array B. She only wants to know the M-th largest element in the array B. Please help her to find this number.
For each test case, the first line contains three positive numbers N(1≤N≤105),K(1≤K≤N),M. The second line contains N numbers Ai(1≤Ai≤109).
It's guaranteed that M is not greater than the length of the array B.
题意:有个数列包含n个数,现在从这个数列中取出所有子区间中的第k大的数(所有长度大于等于k的子区间),构成一个新的数列,求这个新的数列的第M大的数?
思路:我们可以利用尺取求出区间第k大数大于等于x的这样的区间有多少个,然后根据这个进行二分求出准确的第M大数,时间复杂度O(n*log n)。
代码如下:
#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> using namespace std; typedef long long LL; const int N=1e5+5; int a[N],b[N]; LL get(int x,int n,int k) { LL ans=0; int pos=1; int num=0; for(int i=1;i<=n;i++) { if(a[i]>=x) num++; if(num==k) { ans+=n-i+1; while(a[pos]<x) { ans+=n-i+1; pos++; } num--; pos++; } } return ans; } int main() { int T; cin>>T; while(T--) { int n,k; LL m; scanf("%d%d%lld",&n,&k,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]), b[i]=a[i]; sort(b+1,b+n+1); int num=unique(b+1,b+n+1)-(b+1); int L=1,R=num; while(L<=R) { int mid=(L+R)>>1; LL tmp=get(b[mid],n,k); if(tmp<m) R=mid-1; else L=mid+1; } printf("%d\n",b[L-1]); } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:自我介绍
- HDU-2955-Robberies(0-1背包) 2020-03-30
- hdu1455 拼木棍(经典dfs) 2020-02-29
- anniversary party_hdu1520 2020-02-16
- hdu1062 text reverse 2020-01-27
- hdu4841 2020-01-26
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash