减法

Time Limit: 10 Sec Memory Limit: 256 MB

Description

给你一个n个数的序列A，并且给出m次操作B。

操作的含义是：每次从A中选出不同的B_i个数，把它们减去1。一个数>0被看作是可以选择的。

问最多执行完第几个操作。

Input

第一行给出两个整数，序列长度n与操作数m。

第二行n个数，表示序列A。

第三行m个数，表示操作序列B。

Output

输出一个整数，表示最多执行完第几个操作。

Sample Input

3 4
　　2 1 3
　　3 1 2 1

Sample Output

3

HINT

1 <= n, m <=100000

Solution

考虑贪心，显然是每次减去大的数。

我们二分答案做到第几次，然后构造一组不上升序列times，表示每个数最多可以被减几次，每次把区间**[1, B[i]]**加一。

如果每个数都足够大的话，这显然是一组合法解。但是每个数不一定都够减。

我们可以基于这个序列来做调整，考虑什么情况下是合法的呢？
　　显然，前面不够减的可以是分摊到后面去，而若A从大到小排序，贪心尽量多减，那么后面减的次数又不可能比前面多，所以这样就保证了合法性。

所以先把A从大到小排序然后**O(n)**递推。

每次 left += times[i] - A[i]。
　　　　如果left<=0，表示这个位置的值减完还有剩余，但是这个left不能分摊给后面用，所以我们把left设为0；
　　　　如果left>0，可以把left留在后面减，传递下去即可。

递推完只要判断一下最后是否left<=0。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

const int ONE = 1000005;
const int MOD = 1e9 + 7;

int n, m;
int A[ONE], B[ONE];
int times[ONE];
bool cmp(int a, int b) {return a > b;}

int get()
{
    int res=1,Q=1;  char c;
    while( (c=getchar())<48 || c>57)
        if(c=='-')Q=-1;
    if(Q) res=c-48;
    while((c=getchar())>=48 && c<=57)
        res=res*10+c-48;
    return res*Q;
}

int Check(int mid)
{
    for(int i = 1; i <= n; i++) times[i] = 0;
    for(int i = 1; i <= mid; i++)
    {
        times[1]++, times[B[i] + 1]--;
        if(B[i] > n) return 0;
    }

    int left = 0;
    for(int i = 1; i <= n; i++)
    {
        times[i] += times[i - 1];
        left += times[i] - A[i];
        if(left <= 0) left = 0;
    }

    return left <= 0;
}

int main()
{
    n = get();    m = get();
    for(int i = 1; i <= n; i++) A[i] = get();
    for(int i = 1; i <= m; i++) B[i] = get();
    sort(A + 1, A + n + 1, cmp);

    int l = 0, r = m;
    while(l < r - 1)
    {
        int mid = l + r >> 1;
        if(Check(mid)) l = mid;
        else r = mid;
    }

    if(Check(r)) printf("%d", r);
    else printf("%d", l);
}