拼多多 4.12 笔试真题 - 暑期实习

import sys
input = sys.stdin.readline

def solve():
    n, m = map(int, input().split())
    # 差分数组，下标 1..n
    d = [0] * (n + 2)
    for _ in range(m):
        l, r = map(int, input().split())
        d[l] += 1
        d[r + 1] -= 1
    # 前缀和还原每条赛道的水泥段数
    best, best_id, cur = -1, 1, 0
    for i in range(1, n + 1):
        cur += d[i]
        if cur > best:
            best = cur
            best_id = i
    # 总耗时 = 2*m - 水泥段数
    print(2 * m - best, best_id)

solve()

import sys
input = sys.stdin.readline

def check(x, n, d):
    """贪心检查：最小距离至少为 d 时能否放下 n 个偶像"""
    cnt, last = 1, x[0]
    for i in range(1, len(x)):
        if x[i] - last >= d:
            cnt += 1
            last = x[i]
            if cnt >= n:
                return True
    return cnt >= n

def solve(x, n):
    x.sort()
    lo, hi = 0, x[-1] - x[0]
    while lo < hi:
        # 上取整避免死循环
        mid = lo + (hi - lo + 1) // 2
        if check(x, n, mid):
            lo = mid
        else:
            hi = mid - 1
    return lo

T = int(input())
for _ in range(T):
    k, n = map(int, input().split())
    x = list(map(int, input().split()))
    print(solve(x, n))

import sys
input = sys.stdin.readline
from bisect import bisect_right

def solve():
    N, M, s = map(int, input().split())
    pos = list(map(int, input().split()))
    energy = list(map(int, input().split()))
    # 按距离分成左右两侧
    left_side, right_side = [], []
    for i in range(M):
        if pos[i] < s:
            left_side.append((s - pos[i], energy[i]))
        else:
            right_side.append((pos[i] - s, energy[i]))
    left_side.sort()
    right_side.sort()

    def build(side):
        """构建距离数组和能源前缀和"""
        dist, pre = [0], [0]
        for d, e in side:
            dist.append(d)
            pre.append(pre[-1] + e)
        return dist, pre

    l_dist, l_sum = build(left_side)
    r_dist, r_sum = build(right_side)
    ln, rn = len(left_side), len(right_side)

    ans = 0
    # 枚举左侧取前 i 个，二分右侧可达范围
    for i in range(ln + 1):
        l_cost = l_dist[i]
        # 先左后右：燃料消耗 2*l_cost + r_cost
        remain = N - 2 * l_cost
        if remain >= 0:
            j = bisect_right(r_dist, remain) - 1
            ans = max(ans, l_sum[i] + r_sum[j])
        # 先右后左：燃料消耗 l_cost + 2*r_cost
        remain = N - l_cost
        if remain >= 0:
            j = bisect_right(r_dist, remain // 2) - 1
            ans = max(ans, l_sum[i] + r_sum[j])

    # 枚举右侧取前 j 个，二分左侧可达范围
    for j in range(rn + 1):
        r_cost = r_dist[j]
        # 先右后左：燃料消耗 2*r_cost + l_cost
        remain = N - 2 * r_cost
        if remain >= 0:
            i = bisect_right(l_dist, remain) - 1
            ans = max(ans, l_sum[i] + r_sum[j])
    print(ans)

T = int(input())
for _ in range(T):
    solve()

import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    freq = list(map(int, input().split()))
    adj = [[] for _ in range(n)]
    for _ in range(n - 1):
        u, v = map(int, input().split())
        adj[u].append(v)
        adj[v].append(u)
    crystal = [1] * n
    # 按频率从小到大排序节点
    order = sorted(range(n), key=lambda x: freq[x])
    for u in order:
        for v in adj[u]:
            # 频率更低的邻居已确定，当前节点必须比它多
            if freq[v] < freq[u]:
                crystal[u] = max(crystal[u], crystal[v] + 1)
    print(sum(crystal))

solve()