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

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

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=;
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++n,l)-suf;
    int r1=lower_bound(pre,pre++n,l)-pre-;
    int l2=upper_bound(suf,suf++n,r)-suf;
    int r2=upper_bound(pre,pre++n,r)-pre-;
    if(l1>n || !r2) return -;
    if(l1>r1 && l2>r2) return -;
    if(l1<=r1) return l1; else return l2;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=;i<=n;i++) scanf("%d",&a[i]);
    sort(a+,a++n);
    for(int i=;i<=n;i++)
    {
        pre[i]=pre[i-]+a[i];
        suf[i]=suf[i-]+a[n-i+];
    }
    while(m--)
    {
        scanf("%lld%lld",&l,&r);
        printf("%d\n",solve());
    }
    return ;
}