本文共 781 字，大约阅读时间需要 2 分钟。

K-th Number HDU - 6231 

题意：给你n个数字，把所有区间中第k大的数字放在一起构成一个新的数组，如果选取的区间长度小于k则忽略不计，输出新数组中第m大的数字

思路：这个题目可以通过二分来实现，通过二分答案的大小。我们使用取尺法对原数组进行处理，如果我们当前验证答案x是否满足要求，我们可以先选取大于等于x的k个数字，如果前面大于等于x的数字的个数为k，则后面的区间都可以满足条件，然后我们在对去区间的开头进行改变， 对满足条件的区间进行计数，如果满足条件的区间的个数大于等于m则我们可以需要让答案变得大一些，如果小于m我们可以让答案小一些。

#include
   
    using namespace std;const int maxn=1e5+50;int a[maxn];int n,k;long long m;long long  check(int x){    int ans=0;    int st=1;    int num=0;    long long  res=0;    for(int i=1; i<=n; i++)    {        if(a[i]>=x) num++;        if(num==k)        {            res+=n-i+1;            while(a[st]
    
     =m)            {                ans=mid;                l=mid+1;            }            else            {                r=mid;            }        }        printf("%d\n",ans);    }}
    
   

转载地址：http://gbgsi.baihongyu.com/