ACM刷题之路（十九）二分+尺取 2019暑期集训 HDU6231 K-th Number

清疚 2024-02-19 20:35 19阅读 0赞

[题目链接：传送门][Link 1]

**题意：输入N,M,K，第二行输入N个数字，假设第二行是A数组，那么从A数组中所有连续且长度大于等于M的子区间 的 第M大的数字，放入B数组(可重复),最后输出B数组中第K大的数字。**

样例：

5 3 2

2 3 1 5 4

**子区间 2 3 1、3 1 5、 1 5 4、2 3 1 5、 3 1 5 4、2 3 1 5 4的第3大的数分别是1 1 1 2 3 3，所以第二大的数字是3 输出即可**

最暴力的是一一取出长度大于M的区间，再组成B数组，然后求第K大的数，那肯定超时。

这里用到**二分加尺取**的方法

第一步：**B数组的元素肯定来自于A数组**，并且来自于A数组某个区间第M大的数字

第二步：**B数组元素最小是A数组的最小值，最大值是A数组的最大值**，即可以二分

第三步：s=min(A),e=max(A);while(s<e)\{\} 开启二分 对于s和e的 mid值 **运用尺取法进行判断和答案k比较**

第四步：**对于每一个mid，需要找出有多少个区间满足区间内mid至少排第M位**

比如样例 2 3 1 5 4 第一次二分mid=(1+5)/2=3, 那么3在\[2\]中排第0位

(假设排序规则是有x个数大于等于它，那么这个数就排第几位)

同理3在\[2，3\]中排第一位， 3在\[2，3，1\]中第一位, 3在\[2，3，1，5\]中排第二位，在\[2，3，1，5，4\]中排第三位......

所以可以得出区间\[2，3，1，5，4\]满足3>=3，即这个区间的第M位大于等于枚举的mid，即B数组中排mid的右边或者重合

**题目要求输出B数组中第k大的数字，我们只要满足对于每一个二分到的mid值，其右边的数(B数组中)小于k即可。**

如果大于，说明枚举到的mid值在B数组中靠左了，让s=mid+1，否则让e=mid;

PS：有一个可以优化的地方 就 是  **ans += n - e;**

设想\[2 3 1 5 4\]中3排第三位 ，如果在该区间的右边再加上比3小的数字，3还是排第三位。

如果加上比3大的数字，那么3可能会排第Y位，这个Y必定大于等于三，即加数字后的区间的第M位在B数组中一定在mid的右边。

有点烧脑，理解了就很简单了，代码如下：

#include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<vector>
    using namespace std;
    int a[100010];
    vector<int>v;
    int n, m;
    long long k;
    long long fx(int x) {
    	long long ans = 0;
    	int s = 0, e = -1, no = 0;//no比x大于等于的数字有多少
    	while (e < n) {
    		if (no < m) {
    			e++;
    			if (a[e] >= x) {
    				no++;
    			}
    		}
    		else {
    			if (no == m) {
    				ans += n - e;
    			}if (a[s] >= x) no--;
    			s++;
    		}
    	}
    	return ans;
    }
    int main()
    {
    	int t;
    	scanf_s("%d", &t);
    	while (t--) {
    		scanf_s("%d%d%lld", &n, &m, &k);
    		for (int i = 0; i < n; i++) {
    			scanf_s("%d", &a[i]);
    			v.push_back(a[i]);
    		}
    		sort(v.begin(), v.end());
    		int len = unique(v.begin(), v.end()) - v.begin();
    		int s = 0, e = len, ans = -1;
    		while (s < e) {
    			int mid = (s + e) / 2;
    			if (fx(v[mid])>=k) {
    				s = mid + 1;
    				ans = v[mid];
    			}
    			else {
    				e = mid;
    			}
    		}
    		printf("%d\n", ans);
    	}
    	return 0;
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=6231