Description

现在你有 N 个数，分别为 A1,A2,…,AN ，现在有M组询问需要你回答。每个询问将会给你一个L和R (L<=R) ，保证 MaxAi−MinAi<=R−L ，你需要找出并输出最小的K( 1<=K<=N ，不存在输出-1)满足以下两个条件：
①能够在原来的N个数中选出不重复(下标不重复)的K个数，使得这K个数的和在区间 [L,R] 内。
②能够在原来的N个数中选出不重复(下标不重复)的K个数，使得这K个数的和不在区间 [L,R] 内。

Input

输入第一行两个正整数 N,M 。
第二行N个数，表示 A1,A2,…,AN
接下来M行表示M组询问，每组询问两个正整数L,R，意义如上。

Output

输出共M行，每一行输出对应询问的最小的K(不存在输出-1)。

Sample Input

5 3
3 6 5 8 7
29 34
2 8
1 10

Sample Output

-1
2
2

Data Constraint

JZOJ 4932. 【NOIP2017提高组模拟12.24】B

Solution

首先，能满足条件②的，显然满足组合的最大值> R 或者最小值< L 即可
那么先将A数组从小到大排一次序，前 k 个即为最小值，后 k 个即为最大值
设前缀 pre[k] 表示 排序后A数组中前 k 个数的和
设后缀 suf[k] 表示 排序后A数组中后 k 个数的和
那么这两个数组可以 O(N) 预处理出，即可简单判断条件②。
现在问题是如何解决条件①？
观察题目中有这样一句话： MaxAi−MinAi<=R−L
这说明任意的两个 A[i] 相差不会超过 R−L
也就是说，排序后相邻的两种组合的差一定不会同时跨过 L，R
所以，只要 [pre[k],suf[k]] 这个区间与 [L,R] 有交集，那么就一定满足条件①
所以 pre[k]<L≤suf[k] 或 pre[k]≤R<suf[k] 即可
那么这四个不等式，就分别对应着 k 的四个边界 l1,r1,l2,r2
且 l1<r1<l2<r2
可以愉快地发现他们可以二分出来—— O(logN)
因为 [l1,r1] 和 [l2,r2] 是合法的
那么如果 [l1,r1] 合法就选 l1 ，否则如果 [l2,r2] 合法就选 l2 。
要是都不合法，就只能输出 −1 了。
这样总的时间复杂度就是 O(MlogN) ，完美解决！

Code

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100001;
int n,m;
int a[N];
long long pre[N],suf[N];
long long l,r;
inline int solve()
{
int l1=lower_bound(suf,suf+1+n,l)-suf;
int r1=lower_bound(pre,pre+1+n,l)-pre-1;
int l2=upper_bound(suf,suf+1+n,r)-suf;
int r2=upper_bound(pre,pre+1+n,r)-pre-1;
if(l1>n || !r2) return -1;
if(l1>r1 && l2>r2) return -1;
if(l1<=r1) return l1; else return l2;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    sort(a+1,a+1+n);
for(int i=1;i<=n;i++)
    {
        pre[i]=pre[i-1]+a[i];
        suf[i]=suf[i-1]+a[n-i+1];
    }
while(m--)
    {
scanf("%lld%lld",&l,&r);
printf("%d\n",solve());
    }
return 0;
}

秒客网