K-th Number(尺取)

简介: K-th Number(尺取)

题意:有T组数据。 每组数据给定长度为 N的数组 A,对所有长度大于等于 k 的连续子段,取出其第 k 大放入数组 B 中。求数组 B 的第 M 大。
思路:二分答案x检查可行性,x是B数组的第M大所以B数组就有M个大于等于x的数,求有多少个大于X的数就是求有多少个区间的第K大大于X。s[i]表示从1-i大于等于X的数量利用这个求一个区间的第K大是否大于x,再通过尺取长度为K的区间即可。

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const  int N=1e5+10;
ll n,m,k,t;
int a[N];
int s[N];//1-i多少个数大于等于x
bool check(int x)
{
    ll sum=0;
    for(int i=1;i<=n;i++)
    {
        s[i]=s[i-1]+(a[i]>=x);
    }
  int l=1;
   for(int r=k;r<=n;r++)//想想这里怎么做
   {
       while(s[r]-s[l-1]>=k) l++;
       sum+=l-1;
   }
   return sum>=m;
}
int main()
{
    scanf("%lld",&t);
    while(t--)
    {
  scanf("%lld%lld%lld",&n,&k,&m);
    int l=1,r=1;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        r=max(r,a[i]);
    }
    //b m个数大于等于x
     while(l<r)
     {
         int mid=l+r+1>>1;
         if(check(mid)) l=mid;
         else r=mid-1;
     }
        cout<<l<<endl;
    }
   return 0;
}


目录
相关文章
|
8月前
NC14301 K-th Number
NC14301 K-th Number
|
10月前
ACM刷题之路(十九)二分+尺取 2019暑期集训 HDU6231 K-th Number
ACM刷题之路(十九)二分+尺取 2019暑期集训 HDU6231 K-th Number
|
6月前
|
算法
Leetcode 313. Super Ugly Number
题目翻译成中文是『超级丑数』,啥叫丑数?丑数就是素因子只有2,3,5的数,7 14 21不是丑数,因为他们都有7这个素数。 这里的超级丑数只是对丑数的一个扩展,超级丑数的素因子不再仅限于2 3 5,而是由题目给定一个素数数组。与朴素丑数算法相比,只是将素因子变了而已,解法还是和朴素丑数一致的。
66 1
|
11天前
|
存储 算法
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
8 0
|
6月前
|
存储
Leetcode Single Number II (面试题推荐)
给你一个整数数组,每个元素出现了三次,但只有一个元素出现了一次,让你找出这个数,要求线性的时间复杂度,不使用额外空间。
22 0
LeetCode 136. 只出现一次的数字 Single Number
LeetCode 136. 只出现一次的数字 Single Number
LeetCode contest 177 5169. 日期之间隔几天 Number of Days Between Two Dates
LeetCode contest 177 5169. 日期之间隔几天 Number of Days Between Two Dates
|
算法
LeetCode 414. Third Maximum Number
给定一个非空数组,返回此数组中第三大的数。如果不存在,则返回数组中最大的数。要求算法时间复杂度必须是O(n)。
68 0
LeetCode 414. Third Maximum Number
|
存储
LeetCode 313. Super Ugly Number
编写一段程序来查找第 n 个超级丑数。 超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。
67 0
LeetCode 313. Super Ugly Number