凉宫春日的叹息 [思维+二分]

• 2020 年 8 月 14 日
• 筆記
• 二分, 集训日常

凉宫春日的叹息

挺好的思维题。

题目描述

给定一个数组，将其所有子区间的和从小到大排序，求第 \(k\) 小的是多少。

输入格式

第一行两个数 \(n\) , \(k\) ，表示数组的长度和 \(k\)；

第二行有 \(n\) 个数，第\(i\)个是\(a[i]\)，表示给定的数组。

输出格式

仅一个数，表示答案。

样例

样例输入 #1

5 6
1 1 1 1 1

样例输出 #1

2

样例输入 #2

8 20
2 3 1 2 5 3 2 3

样例输出 #2

8

数据范围与提示

对于\(15\%\)的数据，\(n\leqslant 1000\)
对于\(30\%\)的数据，\(n\leqslant 5000\)
对于\(50\%\)的数据，\(n,k\leqslant 10^5\)
对于\(70\%\)的数据，\(n\leqslant 10^5\)
对于\(100\%\)的数据，\(n\leqslant 10^6,1\leqslant a[i],k\leqslant 10^9\)

分析

思路挺难看出来的，但是看出来就很好写了。

首先我们看到 \(k\) 的范围是 \(k\leqslant 10^9\) ，那么直接枚举前 \(k\) 大肯定是不行的，数组都开不下。但是最后的目的还是要去找到第 \(k\) 小的那个数，那么我们可以换一种枚举的方式：枚举值。

枚举排名不现实，所以我们就可以枚举当前第 \(k\) 小的可能值，然后判断一下他的排名到底是比 \(k\) 大还是比 \(k\) 小，然后二分答案即可。

求第几大的时候我们只需要枚举右端点，然后双指针搞一下就行。

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e6+10;
#define ll long long
ll a[maxn];
int n,k;
ll jud(ll mid){//判断当前值排名第几
	ll ans = 0;
	int j = 0;
	for(int i=1;i<=n;++i){
		while(a[i] - a[j] > mid)j++;//枚举右端点，更新双指针
		ans += i - j;//记录排名
	}
	return ans;
}
int main(){
	freopen("A.in","r",stdin);
	freopen("A.out","w",stdout);
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;++i){
		scanf("%lld",&a[i]);
		a[i] += a[i-1];
	}
	ll l = 0,r = a[n];
	while(l < r){//二分答案
		ll mid = l + r >> 1;
		if(jud(mid) >= k)r = mid;//排名比k大就缩小值
		else l = mid + 1;//否则增加
	}
	printf("%lld\n",l);
	return 0;
}