金題大戰Vol.0 A、涼宮春日的嘆息

• 2020 年 8 月 14 日
• 筆記
• 基礎--二分查找

金題大戰Vol.0 A、涼宮春日的嘆息

題目描述

給定一個數組，將其所有子區間的和從小到大排序，求第 \(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 \leq 1000\)

對於\(30\%\)的數據，\(n \leq 5000\)

對於\(50\%\)的數據，\(n,k \leq 10^5\)

對於\(70\%\)的數據，\(n\leq 10^5\)

對於\(100\%\)的數據，\(n\leq 10^6,1 \leq a[i],k \leq 10^9\)

分析

首先，這一道\(k\)的範圍很大，因此我們肯定不可以把前\(k\)小的都求出來

所以我們只能換一種思路

我們觀察一下數據範圍，發現 \(n\) 只有 \(10^6\)，而時限是 \(2s\)

似乎 \(n log n\) 的演算法就可以過

於是我們就嘗試二分枚舉一個數，判斷它能不能作為第 \(k\) 小的值

然後又會發現因為前綴和是單調遞增的，所以就可以用雙指針搞一下

這樣每一次判斷的複雜度就降低到了 \(O(n)\)

程式碼

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e6+5;
typedef long long ll;
inline ll read(){
	ll x=0,f=1;
	char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9'){
		x=(x<<1LL)+(x<<3LL)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
ll n,k,a[maxn],q[maxn],sum[maxn];
bool jud(ll now){
	memset(q,0,sizeof(q));
	ll head=1,tail=0,ans=0;
	for(ll i=1;i<=n;i++){
		while(head<=tail && sum[i]-sum[q[head]-1]>now) head++;
		q[++tail]=i;
		if(sum[i]-sum[q[head]-1]<=now)ans+=(i-q[head]+1);
	}
	return ans>=k;
}
int main(){
	freopen("A.in","r",stdin);
	freopen("A.out","w",stdout);
	n=read(),k=read();
	ll mmin=0x3f3f3f3f3f3f3f3f;
	for(ll i=1;i<=n;i++){
		a[i]=read();
		mmin=min(mmin,a[i]);
		sum[i]=sum[i-1]+a[i]*1LL;
	}
	ll l=mmin,r=sum[n],mids;
	while(l<=r){
		mids=(l+r)/2;
		if(jud(mids)) r=mids-1;
		else l=mids+1;
	}
	printf("%lld\n",l);
	return 0;
}