P1083 [NOIP2012 提高组] 借教室

发表于 更新于 分类于 本文字数： 286 阅读时长 ≈ 1 分钟

先check是不是完全满足，不是再二分订单查找不满足的订单

一开始写得像个弱智一样，check函数最后累加时for循坏竟写成

1
2
3
4
5
6
7
...
#define f(i, a, b) for (int i = a; i <= b; i++)
...
int check(int md){
f(i, 1, md)
...
}

而实际上边界值应该是n

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 <stdio.h>
#include <stdlib.h>

#define scan(x) scanf("%d", &x)
#define f(i, a, b) for (int i = a; i <= b; i++)
#define pn(x) printf("%def\n", x)
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define max 1000086
int n, m, rent[max], mark = 0, d[max], s[max], e[max], diff[max], wa = 1;

int check(int md)
{
    int sum = 0;
    if (md > mark)
        f(i, mark + 1, md)
        {
            diff[s[i]] -= d[i];
            diff[e[i] + 1] += d[i];
        }
    else
        f(i, md + 1, mark)
        {
            diff[s[i]] += d[i];
            diff[e[i] + 1] -= d[i];
        }
    mark = md;
    f(i, 1, n)
    {
        sum += diff[i];
        if (sum < 0)
            return 0;
    }
    return 1;
}

int main()
{
    //IN;
    //OUT;
    scan(n);
    scan(m);
    f(i, 1, n)
        scan(rent[i]);
    f(i, 1, m)
    {
        scan(d[i]);
        scan(s[i]);
        scan(e[i]);
    }
    diff[1] = rent[1];
    f(i, 2, n)
        diff[i] = rent[i] - rent[i - 1];
    if (check(m))
    {
        printf("0");
        return 0;
    }
    int left = 1, right = m, mid; //二分
    while (left <= right)
    {
        mid = (left + right) / 2;
        if (check(mid))
            left = mid + 1;
        else
            right = mid - 1;
    }
    printf("-1\n%d", right + 1);
    return 0;
}