[4-树] P1937 Barn Allocation G - 线段树+贪心

题目描述

• 农夫约翰最近开了一个新的牲口棚屋，并且现在接受来自奶牛的分配畜栏请求因为其中的一些畜栏有更好风景。

• 畜栏包括N个畜栏(1 ≤ N ≤ 100,000)，方便起见，我们把它们编号为1…N，畜栏i能容纳Ci只牛(1 ≤ Ci ≤ 100,000)，第i只牛需要连续编号畜栏（从Ai到Bi）来漫步其中，(1 ≤ Ai ≤ N; Ai ≤ Bi ≤ N)，换言之，这只牛想要在编号范围为Ai…Bi的畜栏漫步（所有它想要畜栏必须实施为它空出位置来供它散步）

• 给出M个畜栏分配请求（1 ≤ M ≤ 100,000），回答最多能满足多少只牛的要求（不增加另外畜栏）

考虑以下例子：

畜栏号:    1   2   3   4   5
           +---+---+---+---+---+
容纳空间:  | 1 | 3 | 2 | 1 | 3 |  
           +---+---+---+---+---+
Cow 1       XXXXXXXXXXX             (1, 3)
Cow 2           XXXXXXXXXXXXXXX     (2, 5)
Cow 3           XXXXXXX             (2, 3)
Cow 4                   XXXXXXX     (4, 5)

约翰显然不能满足所有的牛，因为畜栏3，4请求太多了

经过试验，我们发现，我们能满足牛1，3，4需要，所以这组数据答案为3

输入描述

• 第一行包括两个以空格隔开的正整数：N,M

• 第二行到第N+1行：第i+1行包括一个整数：Ci

• 第N+2到第N+M+1行：第i+N+1 包括两个整数Ai、Bi

输出描述

仅一行：能满足的最大需要

测试样例

样例1:输入-输出-解释

输入：
5 4
1
3
2
1
3
1 3
2 5
2 3
4 5
输出：
3

分析

• 此题把棚屋作为原数组进行维护，需要维护的是 一段区间内的最小值， 因为对于每一只牲口，其活动空间 [Ai, Bi] 都是一个区间，所有被此区间包围的区间，其最小值必须大于0，否则不可以放入
• 贪心法选择放入：将奶牛的路径转化为线段，以右端点为第一关键字，左端点为第二关键字，按第一关键字从小到大排序，若第一关键字相同则按第二关键字从大到小排序。
  • 贪心法的依据：
    

代码

INF = 99999999


def build(tree: [int], ori: [int], l: int, r: int, pos: int):
    if l == r:
        tree[pos] = ori[l-1]
        return
    mid = (l + r) // 2
    build(tree, ori, l, mid, 2*pos+1)
    build(tree, ori, mid+1, r, 2*pos+2)
    tree[pos] = min(tree[2*pos+1], tree[2*pos+2])

def queryMin(tree: [int], l: int, r: int, needl: int, needr: int, pos: int) -> int:
    if needr < l or needl > r:
        return INF
    if needl <= l and needr >= r:
        return tree[pos]
    mid = (l+r) // 2
    return min(queryMin(tree, l, mid, needl, needr, 2*pos+1), queryMin(tree, mid+1, r, needl, needr, 2*pos+2))

def insertCow(tree: [int], l: int, r: int, needl: int, needr: int, pos: int):
    if needl <= l <= needr and l == r:
        tree[pos] -= 1
        return
    if needr < l or needl > r:
        return
    mid = (l+r)//2
    insertCow(tree, l, mid, needl, needr, 2*pos+1)
    insertCow(tree, mid+1, r, needl, needr, 2*pos+2)
    tree[pos] = min(tree[2*pos+1], tree[2*pos+2])
    return



if __name__ == '__main__':
    x = input().strip().split()
    n = int(x[0]) # fence
    m = int(x[1]) # cowreqs
    fences = []
    cowreq = []
    for i in range(n):
        fences.append(int(input()))
    for i in range(m):
        x = input().strip().split()
        # Ai, Bi
        cowreq.append([int(x[0]), int(x[1])])
    # 排序
    cowreq = sorted(cowreq, key=lambda vi: (vi[1], (vi[1] - vi[0])))
    tree = [0 for i in range(4*n+1)]
    build(tree, fences, 1, n, 0)
    cnt = 0
    for i in cowreq:
        minVal = queryMin(tree, 1, n, i[0], i[1], 0)
        if minVal > 0:
            insertCow(tree, 1, n, i[0], i[1], 0)
            cnt += 1
    print(cnt)

参考

Luogu P1937