51Nod-1686-第K大区间

2022-02-23 题解

简单一想就能知道这题很难直接求出答案，而这个“求第K大”的特性又比较符合二分答案类型题的特性，所以这题应尝试使用二分答案来写。

怎么验证答案x是否可行？注意到：如果原序列的一个子串的值大于等于x，那么与这个子串起点相同，终点在这个子串右边的子串也都大于等于x了。这样就可以快速地得到以某个数（假设为head）为起点，且值大于等于x的区间的个数了。

但是，把head从1到n枚举一遍还是有点慢了。当处理完以head为区间的起点后，只要把当前“状态”下的head删掉，就可以得到以head + 1为起点的区间的状态了。这其实就是一个滑动窗格（尺取）的过程。具体会在代码中注释。

在算众数的时候需要用到各个数值出现过的次数，由于数值很大，这里用了离散化，p[i]表示：若每个数值只出现一次，a[i]的值在整个序列中排第p[i]大。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
long long a[100005], b[100005], p[100005], n, k, m;
long long sum[100005]; //仅在C函数中用到，sum[p[i]]表示值与a[i]相等的元素出现过的次数
bool C(long long x)
{
    int head = 1, end; //滑动窗格的起点和终点

    long long ret = 0; //值大于x的元素个数

    for (int i = 1; i <= n; i++)
        sum[i] = 0; //初始化

    for (end = 1; end <= n; end++)
    {
        sum[p[end]]++; //值为a[end]的数多了一个

        while (sum[p[end]] >= x) //如果当前滑动窗格满足条件就一直缩小滑动窗格
        {
            ret += n - end + 1;
            //把滑动窗格的起点往右移
            sum[p[head]]--;
            head++;
        }
    }

    return ret >= k;
}
int main()
{
    scanf("%d%d", &n, &k);
    int i;
    for (i = 1; i <= n; i++)
    {
        scanf("%lld", &a[i]);
        b[i] = a[i];
    }
    sort(b + 1, b + 1 + n);
    m = unique(b + 1, b + 1 + n) - b - 1;
    for (i = 1; i <= n; i++)
        p[i] = lower_bound(b + 1, b + 1 + m, a[i]) - b;
    long long l = 1, r = n + 1, m;
    while (r - l > 1)
    {
        m = ((l + r) >> 1);
        if (C(m))
            l = m;
        else
            r = m;
    }
    printf("%lld", l);
    return 0;
}