51Nod——T 1686 第K大区间

https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1686

基准时间限制：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 （logn）
枚举一个右端点，记录[l,r]之间每个数的出现个数（离散化，map统计）
如果一个数在[l,r]中的出现个数>=x，则 当 r 属于[r+1,n] 中时，同样满足
满足时，不断缩小l，判断每个区间的情况 （o(n)）
nlogn

 #include <algorithm>

 #include <cstring>

 #include <cstdio>

 inline void read(int &x)

 {

     x=; register char ch=getchar();

     for(; ch>''||ch<''; ) ch=getchar();

     for(; ch>=''&&ch<=''; ch=getchar()) x=x*+ch-'';

 }

 const int N();

 int n,k,b[N];

 struct Node {

     int num,id;

     bool operator < (const Node&x)const

     {

         return num<x.num;

     }

 }a[N];

 int L,R,Mid,ans,cnt[N];

 inline bool check(int x)

 {

     memset(cnt,,sizeof(cnt));

     int l=,r=,ret=;

     for(; r<=n; ++r)

     {

         cnt[b[r]]++;

         if(cnt[b[r]]>=x)

         {

             ret+=n-r+;

             cnt[b[l++]]--;

             for(; cnt[b[r]]>=x&&l<r; )

             {

                 ret+=n-r+;

                 cnt[b[l++]]--;

             }

         }

         if(ret>=k) return ;

     }

     return ;

 }

 int Presist()

 {

     read(n),read(k);

     for(int i=; i<=n; ++i)    read(a[i].num),a[i].id=i;

     std::sort(a+,a+n+);

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

         b[a[i].id]=(a[i].num!=a[i-].num)?++a[].id:a[].id;

     for(L=,R=n; L<=R; )

     {

         Mid=L+R>>;

         if(check(Mid))

         {

             ans=Mid;

             L=Mid+;

         }

         else R=Mid-;

     }

     printf("%d",ans);

     return ;

 }

 int Aptal=Presist();

 int main(int argc,char**argv){;}

巴特西

51Nod——T 1686 第K大区间

https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1686

最新文章

热门文章