【JZOJ4932】【NOIP2017提高组模拟12.24】B

Description

现在你有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]内。

Data Constraint

Solution

我们先来讨论一下怎样才能满足条件2：我们先将A排序。设min[i]表示前i个数的和，max[i]表示后i个数的和。那么显然会有 min[k]<l||max[k]>r 才能合法。
我们再来讨论一下怎样才能满足条件1：由于数据保证Max{Ai}-Min{Ai}<=R-L，所以我们会发现只要存在 [min[k],max[k]]∩[l,r]≠∅ 即合法。化简一下就成 min[k]<=r||max[k]>=l 时合法
简单证明一下
假如min[k]或max[k]在[l,r]内，那么显然可以。
假如min[k]或max[k]不在[l,r]内，那么显然 [l,r]⊆[min[k],max[k]]，由于数据保证MaxAi−MinAi<=R−L ，就说明两两数之间的距离一定不超过r-l，我们一定可以在max[k]通过不断更换里面的数来实现max[k]不断减小直至min[k]，因为max[k]>r,l>min[k]，两两数之间的距离一定不超过r-l，所以在这过程中一定经过[l,r]。
证明完毕
现在我们知道这两个条件，我们强制max[k]>min[k],那么将两条式子统一一下结成了 min[k]<=r<max[k]||min[k]<l<=max[k] 。直接打l,r每边各打两个二分判断一下是否存在这样的k，取个最小的输出即可。没有就输出-1.时间复杂度O( NlogN )

Code

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=1e5+5;
ll a[maxn],f[maxn],g[maxn];
ll n,m,i,t,j,k,l,x,y,r,mid;
bool bz;
int main(){
//freopen("data.in","r",stdin);freopen("data.out","w",stdout);
scanf("%lld%lld",&n,&m);
for (i=1;i<=n;i++)
scanf("%lld",&a[i]);
    sort(a+1,a+n+1);
for (i=1;i<=n;i++)
        f[i]=f[i-1]+a[i];
for (i=n;i>=1;i--)
        g[n-i+1]=g[n-i]+a[i];
for (i=1;i<=m;i++){
scanf("%lld%lld",&x,&y);
        l=0;
        r=n+1;
while (l<r){
            mid=(l+r+1)/2;
if (f[mid]>y) r=mid-1;
else l=mid;
        }
        t=l;
        r=l+1;
        l=0;
while (l<r){
            mid=(l+r)/2;
if (g[mid]>y) r=mid;
else l=mid+1;
        }
if (l==t+1) t=0;
else t=l;
        l=0;
        r=n+1;
while (l<r){
            mid=(l+r+1)/2;
if (f[mid]>x-1) r=mid-1;
else l=mid;
        }
        k=l;
        r=l+1;
        l=0;
while (l<r){
            mid=(l+r)/2;
if (g[mid]>=x) r=mid;
else l=mid+1;
        }
if (l==k+1) k=0;
else k=l;
if (t && k) k=min(t,k);
else k=max(t,k);
if (k && k!=n+1) printf("%d\n",k);
else printf("-1\n");

    }
}