51nod 1686 二分+离散化

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

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
一开始以为是第k大的值，后来发现是第K大区间的值，重复的也要计算在内。
二分k表示区间值大于等于k的区间的个数，个数小于K区间值小于等于k的都在答案的上面，否则说明答案包含在k之上。
在找区间个数的函数内可以使用尺取法，由于要统计出现次数所以进行离散化一下，用mapT了一个点，最后用结构体按照下标映射A掉。

 #include<bits/stdc++.h>

 using namespace std;

 #define LL long long

 struct node

 {

     int v,id;

 }P[];

 bool cmpid(node A,node B){return A.id<B.id;}

 bool cmpv(node A,node B){return A.v<B.v;}

 int M[];

 LL book[];

 LL solve(int k,int n)

 {

     LL s=,l=,maxn=;

     memset(book,,sizeof(book));

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

     {

      LL x=++book[M[i]];

      if(x>maxn)maxn=x;

      if(maxn==k){

         while(maxn==k&&l<=i){

             s+=n-i+;

             LL y=book[M[l]]--;

             if(maxn==y) maxn--;

             l++;

         }

      }

     }

     return s;

 }

 int main()

 {

     int n,i,j,p=;

     LL k;

     cin>>n>>k;

     for(i=;i<=n;++i) scanf("%d",&P[i].v),P[i].id=i;

     sort(P+,P++n,cmpv);

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

     {

        if(P[i].v==P[i-].v) M[P[i].id]=M[P[i-].id];

        else M[P[i].id]=++p;

     }

     sort(P+,P++n,cmpid);

     int l=,r=n;

     while(l<r){

         int mid=r-(r-l)/;

         //cout<<l<<' '<<r<<' '<<mid<<endl;

         if(solve(mid,n)<k) r=mid-;

         else l=mid;

     }

     cout<<l<<endl;

     return ;

 }

巴特西

51nod 1686 二分+离散化

最新文章

热门文章