1686 第K大区间(尺取+二分)

基准时间限制：1 秒空间限制：131072 KB 分值: 40 难度：4级算法题

定义一个区间的值为其众数出现的次数。
现给出n个数，求将所有区间的值排序后，第K大的值为多少。

Input

第一行两个数n和k(1<=n<=100000,k<=n*(n-1)/2)

第二行n个数，0<=每个数<2^31

Output

一个数表示答案。

Input示例

4 2

1 2 3 2

Output示例

2

//首先，考虑区间的值的性质，如果区间的值为 x ，那么，区间无论怎么左右扩展，区间的值必然大于等于 x 。
那么，计算区间的值大于等于 x ，可以用尺取在 O(n) 时间算出，显然，这是有单调性的，二分即可

 # include <cstdio>

 # include <cstring>

 # include <cstdlib>

 # include <iostream>

 # include <vector>

 # include <queue>

 # include <stack>

 # include <map>

 # include <bitset>

 # include <sstream>

 # include <set>

 # include <cmath>

 # include <algorithm>

 # pragma  comment(linker,"/STACK:102400000,102400000")

 using namespace std;

 # define LL          long long

 # define pr          pair

 # define mkp         make_pair

 # define lowbit(x)   ((x)&(-x))

 # define PI          acos(-1.0)

 # define INF         0x3f3f3f3f3f3f3f3f

 # define eps         1e-

 # define MOD         

 inline int scan() {

     int x=,f=; char ch=getchar();

     while(ch<''||ch>''){if(ch=='-') f=-; ch=getchar();}

     while(ch>=''&&ch<=''){x=x*+ch-''; ch=getchar();}

     return x*f;

 }

 inline void Out(int a) {

     if(a<) {putchar('-'); a=-a;}

     if(a>=) Out(a/);

     putchar(a%+'');

 }

 # define MX

 /**************************/

 int n,k;

 int a[MX];

 int b[MX];

 int num[MX];

 bool check(int x)

 {

     memset(num,,sizeof(num));

     int l=,r=,flag=;

     LL tot=;

     while (r<=n+)

     {

         if (!flag)

         {

             if (r==n+) break;

             num[a[r]]++;

             if (num[a[r]]>=x) flag=r;

             r++;

         }

         else

         {

             while (flag)

             {

                 tot += n-r+;

                 num[a[l]]--;

                 if (num[a[flag]]<x) flag=;

                 l++;

             }

         }

     }

     if (tot>=k) return ;

     return ;

 }

 int main()

 {

     scanf("%d%d",&n,&k);

     for (int i=;i<=n;i++)

     {

         scanf("%d",&a[i]);

         b[i] = a[i];

     }

     sort(b+,b++n);

     for (int i=;i<=n;i++)

         a[i] = lower_bound(b+,b++n,a[i])-b;

     int l=, r=n;

     int ans;

     while (l<=r)

     {

         int mid = (l+r)>>;

         if (check(mid)) ans=mid,l=mid+;

         else r=mid-;

     }

     printf("%d\n",ans);

     return ;

 }

巴特西

1686 第K大区间(尺取+二分)

最新文章

热门文章