HDU 6231 (二分+双指针)

题意：给一个长度为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代码