原题链接

Acwing

思路

一开始没有读清题目，以为遇到了一个不满足的人之后会忽略他，继续处理，所以想的复杂了一点。

我们假设实际可以满足的人数为n，处理的人数为x。显然，如果x>n，那么一定不满足；换而言之，可以通过二分来查找最小的一个满足条件的解（也就是n）。

二分本身为对数复杂度，考虑到本题的数据量，二分中判断的复杂度应该是线性的。问题的判定是对一个数组进行x次的区间减法，之后的区间中是否存在负值。如果采用朴素的方法，那么每一次区间减法需要线性复杂度，整体需要平方复杂度，显然 不符合要求。这里需要使用差分的方法，将区间减法变为点减法，时间复杂度也就变为线性复杂度。

实现

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
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
typedef long long ll;
ll S[N];
ll A[N];

struct {
    int l;
    int r;
    int dat;
} interval[N];

bool is_valid(int mid, int len){
    memset(S, 0, sizeof(S));
    S[1] = A[1];
    for(int i=2;i<=len;i++){
        S[i] = A[i]-A[i-1];
    }
    
    for(int i=1;i<=mid;i++){
        S[interval[i].l] -= interval[i].dat;
        S[interval[i].r+1] +=  interval[i].dat;
    }
    
    ll res = 0;
    for(int i=1;i<=len;i++){
        res += S[i];
        if (res<0)return true;
    }                          
    return false;
}

int solve(int arr_len, int interval_len){
    int l = 1, r = interval_len + 1;
    
    while(l<r){
        int mid = (l+r)>>1;
        if(is_valid(mid, arr_len)){
            r = mid; 
        }else{
            l = mid+1;
        }
    }
    
    if (l==interval_len+1)return 0;
    return l;
}

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>A[i];
    }
    
    for(int i=1;i<=m;i++){
        cin>>interval[i].dat>>interval[i].l>>interval[i].r;
    }
    
    int res = solve(n,m);
    if(res){
        cout<<"-1\n"<<res<<endl;
        return 0;
    }
    
    cout<<"0\n";
    return 0;
}