AcWing
  • 首页
  • 活动
  • 题库
  • 竞赛
  • 商店
  • 应用
  • 文章
    • 题解
    • 分享
    • 问答
  • 吐槽
  • 登录/注册

AcWing 1952. 金发姑娘和 N 头牛 0.01 AC币

作者: 作者的头像   秀策 ,  2022-01-15 01:33:24 ,  所有人可见 ,  阅读 19


0


"""
Dict
"""


from collections import defaultdict

INF = 2e9


def main():
    n, x, y, z = map(int, input().split())
    b = defaultdict(int)

    for _ in range(n):
        l, r = map(int, input().split())
        b[-INF] += x
        b[l] += y - x
        b[r + 1] += z - y
        b[INF] -= z

    tot = res = 0
    for i in sorted(b.keys()):
        tot += b[i]
        if res < tot:
            res = tot
    print(res)


main()


"""
手写离散化
"""

from collections import defaultdict

N = 20010
INF = 2e9
xs = [-INF, INF]


def find(x):
    l, r = 0, len(xs) - 1
    while l < r:
        mid = l + r >> 1
        if xs[mid] >= x:
            r = mid
        else:
            l = mid + 1
    return r


def main():
    global xs
    n, x, y, z = map(int, input().split())
    l, r = [0] * n, [0] * n
    b = [0] * N * 2

    for i in range(n):
        l[i], r[i] = map(int, input().split())
        xs.append(l[i])
        xs.append(r[i] + 1)

    xs = sorted(set(xs))

    for i in range(n):
        L = find(l[i])
        R = find(r[i] + 1)
        b[0] += x
        b[L] += y - x
        b[R] += z - y
        b[-1] -= z

    tot = res = 0
    for x in b:
        tot += x
        if res < tot:
            res = tot
    print(res)


main()


"""
待debug代码 
https://www.acwing.com/community/content/624666/
"""


from collections import defaultdict


def main():
    n, x, y, z = map(int, input().split())
    b = defaultdict(int)
    cows = []
    for _ in range(n):
        l, r = map(int, input().split())
        cows.append([l, r])
        b[l] += 1
        b[r] -= 1

    tot = 0
    maxv = float('-inf')
    for i in sorted(b.keys()):
        tot += b[i]
        if maxv < tot:
            maxv = tot

    k = []
    tot = 0
    last = None
    for i in sorted(b.keys()):
        if tot == maxv:
            k.extend([i for i in range(last, i + 1)])
        tot += b[i]
        last = i

    res = 0
    for c in set(k):
        t = 0
        print(f' temperate: c: {c}')

        for l, r in sorted(cows):
            if r < c:
                t += z
                print(l, r, x)
            elif l > c:
                t += z
                print(l, r, z)
            else:
                t += x
                print(l, r, y)

        res = max(res, t)
    print(res)


main()

0 评论

你确定删除吗?
1024
x

© 2018-2022 AcWing 版权所有  |  京ICP备17053197号-1
用户协议  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息