题目

现在你有N个数，分别为A1,A2,…,AN，现在有M组询问需要你回答。每个询问将会给你一个L和R(L<=R)，保证Max{Ai}-Min{Ai}<=R-L，你需要找出并输出最小的K(1<=K<=N，不存在输出-1)满足以下两个条件：

①能够在原来的N个数中选出不重复(下标不重复)的K个数，使得这K个数的和在区间[L,R]内。

②能够在原来的N个数中选出不重复(下标不重复)的K个数，使得这K个数的和不在区间[L,R]内。

分析

首先将A从小到大排个序，那么前k个数的和就是最小的k个数的和，后k个数的和就是最大的k个数的和。

那么设它们分别为\(min(k)\)和\(max(k)\)。

要满足\(②\)，显然只要\(min(k)<L\)或\(R<max(k)\)就可以了；

考虑\(①\)，

注意到"保证Max{Ai}-Min{Ai}<=R-L"

也就是说选的k个数的间隔一定小于\(R-L\)

于是\(min(k)<L<=max(k)\)或\(min(k1)<=R<max(k1)\)，

那么分别二分\(k、k1\)的上下界，\(l1<=k<=r1、l2<=k1<=r2\)

因为k越小越好，

所以如果\(l1\)合法就输出\(l1\)，否则输出\(l2\)。

#include <cmath>

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <queue>

const long long maxlongint=2147483647;

const long long mo=1000000007;

const long long N=100005;

using namespace std;

long long a[N],mx[N],mn[N],n,m;

int main()

{

	scanf("%lld%lld",&n,&m);

	for(long long i=1;i<=n;i++) scanf("%lld",&a[i]);

	sort(a+1,a+1+n);

	for(long long i=1;i<=n;i++) mn[i]=mn[i-1]+a[i],mx[i]=mx[i-1]+a[n-i+1];

	for(long long i=1;i<=m;i++)

	{

		long long l,r;

		scanf("%lld%lld",&l,&r);

		long long l1=lower_bound(mx,mx+1+n,l)-mx,r1=lower_bound(mn,mn+1+n,l)-mn-1;

		long long l2=upper_bound(mx,mx+1+n,r)-mx,r2=upper_bound(mn,mn+1+n,r)-mn-1;

		if(l1==n+1 || r2==0 || l1>r1 && l2>r2) printf("-1\n");

		else

		{

			if(l1>r1) printf("%lld\n",l2);

			else printf("%lld\n",l1);

		}

	}

}

巴特西

【NOIP2017提高组模拟12.24】B

题目

分析

最新文章

热门文章