51nod 1686 第K大区间2

1685 第K大区间2

定义一个区间的值为其众数出现的次数
现给出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

题解:二分答案 尺取法
如果一个区间[l,r]刚刚满足众数出现的次数为k,那么[1-l,r-n]这些区间也会满足。
所以二分一个答案t,检查众数出现次数大于t的区间的个数是否大于k,对于check函数,
我们枚举右端点,如果当右端点为r时众数的出现次数为t,那么对于左端点为l,
有n-r+1个区间的众数的出现次数可能大于t.时间复杂度O(nlogn)
哎..check()函数老写T...
代码:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define LL long long
#define maxn 100009
using namespace std;

int n,k,l,r,mid,ans;
int a[maxn],b[maxn],sum[maxn];

bool check(int p){
    int x=1,y=1,all=0,flag=0;
    memset(sum,0,sizeof(sum));
    while(y<=n){
        if(!flag){
            if(y==n+1)break;
            sum[a[y]]++;
            if(sum[a[y]]==p)flag=y;
            y++;
        }else{
            while(flag){
                all+=n-r+2;
                sum[a[x]]--;
                if(sum[a[flag]]<=p-1)flag=0;
                x++;
            }
        }
    }
    return all>=k;
}

int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+n+1,a[i])-b;
    l=1;r=n;
    while(l<=r){
        mid=(l+r)>>1;
        if(check(mid)){
            ans=mid;l=mid+1;
        }else r=mid-1;
    }
    printf("%d
",ans);
    return 0;
}


原文地址:https://www.cnblogs.com/zzyh/p/7641979.html