登录
OAmaster

A dual-core processor has one process queue per core. There are n processes; time[i] is the processing time of the i-th. There is a latch that decides which core picks. Initially the latch is with core 1. When the latch is held by core c and process i needs to be assigned, one of the two operations must be performed:

  • Assign process i to core c; pass the latch to the other core.
  • Assign process i to the other core; the latch stays with core c.

Each core, when it holds the latch, picks the operation that maximizes its own total accumulated time. Return [total_core1, total_core2] under optimal play.

Example

n = 5
time = [10, 21, 10, 21, 10]
Output: [41, 31]

Constraints

  • 1 ≤ n ≤ 10⁵
  • 1 ≤ time[i] ≤ 10⁹

解法

在 (i, latch) 上做博弈 DP。f(i, c) 表示从下标 i 开始、latch 在 core c 手里、两方均最优时核 1 与核 2 的最终得分对 (a, b)。当前持有 latch 的核 c 在两个转移中选使自己 (a, b)[c-1] 最大的那个。从 i = n(终态 (0, 0))自底向上递推。时间和空间均 O(n)。

def get_process_time(time):
    n = len(time)
    # f[i][c] = (a, b) when start at i, latch = c (c in {1, 2})
    f = [[(0, 0), (0, 0)] for _ in range(n + 1)]
    for i in range(n - 1, -1, -1):
        for c in (1, 2):
            # Option A: assign to core c, latch flips
            a1, b1 = f[i + 1][3 - c - 1] if False else f[i + 1][(3 - c) - 1]
            optA = (a1 + (time[i] if c == 1 else 0),
                    b1 + (time[i] if c == 2 else 0))
            # Option B: assign to the other core, latch stays
            a2, b2 = f[i + 1][c - 1]
            other = 3 - c
            optB = (a2 + (time[i] if other == 1 else 0),
                    b2 + (time[i] if other == 2 else 0))
            f[i][c - 1] = optA if optA[c - 1] >= optB[c - 1] else optB
    return list(f[0][0])  # latch starts at core 1
class Solution {
    static long[] getProcessTime(int[] time) {
        int n = time.length;
        long[][][] f = new long[n + 1][2][2]; // f[i][c-1] = {a, b}
        for (int i = n - 1; i >= 0; i--) {
            for (int c = 1; c <= 2; c++) {
                int other = 3 - c;
                long[] na = f[i + 1][other - 1]; // latch flips to other
                long[] optA = { na[0] + (c == 1 ? time[i] : 0),
                                na[1] + (c == 2 ? time[i] : 0) };
                long[] nb = f[i + 1][c - 1];     // latch stays at c
                long[] optB = { nb[0] + (other == 1 ? time[i] : 0),
                                nb[1] + (other == 2 ? time[i] : 0) };
                if (optA[c - 1] >= optB[c - 1]) f[i][c - 1] = optA;
                else f[i][c - 1] = optB;
            }
        }
        return f[0][0];
    }
}
vector<long long> getProcessTime(vector<int>& time) {
 int n = time.size();
 vector<vector<array<long long, 2>>> f(n + 1, vector<array<long long, 2>>(2, {0, 0}));
 for (int i = n - 1; i >= 0; i--) {
 for (int c = 1; c <= 2; c++) {
 int other = 3 - c;
 auto& na = f[i + 1][other - 1];
 array<long long, 2> optA = { na[0] + (c == 1 ? (long long)time[i] : 0),
 na[1] + (c == 2 ? (long long)time[i] : 0) };
 auto& nb = f[i + 1][c - 1];
 array<long long, 2> optB = { nb[0] + (other == 1 ? (long long)time[i] : 0),
 nb[1] + (other == 2 ? (long long)time[i] : 0) };
 f[i][c - 1] = optA[c - 1] >= optB[c - 1] ? optA : optB;
 }
 }
 return { f[0][0][0], f[0][0][1] };
}

A network of warehouses is an undirected rooted weighted tree with warehouse_nodes nodes rooted at warehouse 1. Each node has a value val[v]. A pair (u, v) is compatible iff:

  • u is an ancestor of v in the tree.
  • distance(u, v) ≤ val[v].

Count compatible pairs.

Example: with the input from the OA, the answer is 5.

Constraints

  • 1 ≤ warehouse_nodes ≤ 1.5·10⁵
  • 1 ≤ warehouse_weight[i] ≤ 10⁴
  • 1 ≤ val[i] ≤ 10⁹

解法

记 D[v] 为根到 v 的带权距离。条件 distance(u, v) = D[v] - D[u] ≤ val[v] 等价于 D[u] ≥ D[v] - val[v]。迭代 DFS，维护当前路径上所有祖先的 D[u] 有序多重集。到达 v 时二分统计满足 D[u] ≥ D[v] - val[v] 的祖先数累入答案；入栈时插入 D[v]，出栈时删除。时间 O(n log n)，空间 O(n)。n = 1.5·10⁵ 时用迭代避免递归爆栈。

from sortedcontainers import SortedList

def count_compatible_pairs(warehouse_nodes, frm, to, weight, val):
    n = warehouse_nodes
    g = [[] for _ in range(n + 1)]
    for a, b, w in zip(frm, to, weight):
        g[a].append((b, w))
        g[b].append((a, w))
    ans = 0
    sl = SortedList()
    # iterative DFS
    stack = [(1, 0, 0, iter(g[1]), 'enter')]
    D = [0] * (n + 1)
    visited = [False] * (n + 1)
    visited[1] = True
    sl.add(0)
    parent = {1: 0}
    order = [1]
    it_stack = [iter(g[1])]
    node_stack = [1]
    while node_stack:
        u = node_stack[-1]
        it = it_stack[-1]
        advanced = False
        for nb, w in it:
            if not visited[nb]:
                visited[nb] = True
                D[nb] = D[u] + w
                # count compatible ancestors of nb
                threshold = D[nb] - val[nb - 1]
                idx = sl.bisect_left(threshold)
                ans += len(sl) - idx
                sl.add(D[nb])
                node_stack.append(nb)
                it_stack.append(iter(g[nb]))
                advanced = True
                break
        if not advanced:
            sl.remove(D[u])
            node_stack.pop()
            it_stack.pop()
    return ans
class Solution {
    static long countCompatiblePairs(int warehouseNodes, int[] from, int[] to, int[] weight, int[] val) {
        int n = warehouseNodes;
        List<int[]>[] g = new List[n + 1];
        for (int i = 1; i <= n; i++) g[i] = new ArrayList<>();
        for (int i = 0; i < from.length; i++) {
            g[from[i]].add(new int[]{to[i], weight[i]});
            g[to[i]].add(new int[]{from[i], weight[i]});
        }
        long[] D = new long[n + 1];
        TreeMap<Long, Integer> ms = new TreeMap<>();
        ms.merge(0L, 1, Integer::sum);
        long ans = 0;
        int[] parent = new int[n + 1];
        int[] iter = new int[n + 1];
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(1);
        parent[1] = 0;
        while (!stack.isEmpty()) {
            int u = stack.peek();
            boolean advanced = false;
            while (iter[u] < g[u].size()) {
                int[] e = g[u].get(iter[u]++);
                int nb = e[0], w = e[1];
                if (nb == parent[u]) continue;
                parent[nb] = u;
                D[nb] = D[u] + w;
                long threshold = D[nb] - val[nb - 1];
                int count = 0;
                for (var entry : ms.tailMap(threshold).entrySet()) count += entry.getValue();
                ans += count;
                ms.merge(D[nb], 1, Integer::sum);
                stack.push(nb);
                advanced = true;
                break;
            }
            if (!advanced) {
                ms.merge(D[u], -1, Integer::sum);
                if (ms.get(D[u]) == 0) ms.remove(D[u]);
                stack.pop();
            }
        }
        return ans;
    }
}
long long countCompatiblePairs(int warehouseNodes, vector<int>& from, vector<int>& to,
 vector<int>& weight, vector<int>& val) {
 int n = warehouseNodes;
 vector<vector<pair<int,int>>> g(n + 1);
 for (size_t i = 0; i < from.size(); i++) {
 g[from[i]].push_back({to[i], weight[i]});
 g[to[i]].push_back({from[i], weight[i]});
 }
 vector<long long> D(n + 1, 0);
 multiset<long long> ms;
 ms.insert(0);
 long long ans = 0;
 vector<int> parent(n + 1, 0), it(n + 1, 0);
 vector<int> stack;
 stack.push_back(1);
 while (!stack.empty()) {
 int u = stack.back();
 bool advanced = false;
 while (it[u] < (int)g[u].size()) {
 auto [nb, w] = g[u][it[u]++];
 if (nb == parent[u]) continue;
 parent[nb] = u;
 D[nb] = D[u] + w;
 long long threshold = D[nb] - val[nb - 1];
 ans += distance(ms.lower_bound(threshold), ms.end());
 ms.insert(D[nb]);
 stack.push_back(nb);
 advanced = true;
 break;
 }
 if (!advanced) {
 ms.erase(ms.find(D[u]));
 stack.pop_back();
 }
 }
 return ans;
}

> Note: the Java/C++ implementations use TreeMap / multiset which give O(log n) insertion and removal but O(n) worst-case tail-count via iteration; for the full constraint use a Fenwick tree over compressed D values.

Given array arr of n integers, the operation is: choose index i (0 ≤ i < n - 1) and swap arr[i] and arr[i + 1]. Each element can participate in at most one swap. Strength of index i is arr[i] * (i + 1) (0-indexed). Maximize the sum Σ arr[i] * (i + 1).

Example

n = 5
arr = [1, 9, 7, 3, 2]
Output: 66 // swap (arr[2], arr[3]) -> [1, 9, 3, 7, 2]

Constraints

  • 1 ≤ n ≤ 10⁵
  • 1 ≤ arr[i] ≤ 10⁵

解法

每个元素至多参与一次交换，所以两次相邻交换不能共享元素，选中的交换位置构成不相交的相邻对。DP：dp[i] 表示长度为 i 前缀的最大力量和。

dp[0] = 0
dp[1] = arr[0] * 1
dp[i] = max(dp[i-1] + arr[i-1] * i,
 dp[i-2] + arr[i-1] * (i-1) + arr[i-2] * i) // 交换位置 i-1, i-2

答案为 dp[n]。复杂度 O(n)。

def get_maximum_sum_of_strengths(arr):
    n = len(arr)
    if n == 0:
        return 0
    dp = [0] * (n + 1)
    dp[1] = arr[0] * 1
    for i in range(2, n + 1):
        keep = dp[i - 1] + arr[i - 1] * i
        swap = dp[i - 2] + arr[i - 1] * (i - 1) + arr[i - 2] * i
        dp[i] = max(keep, swap)
    return dp[n]
class Solution {
    static long getMaximumSumOfStrengths(int[] arr) {
        int n = arr.length;
        if (n == 0) return 0;
        long[] dp = new long[n + 1];
        dp[1] = (long) arr[0] * 1;
        for (int i = 2; i <= n; i++) {
            long keep = dp[i - 1] + (long) arr[i - 1] * i;
            long swap = dp[i - 2] + (long) arr[i - 1] * (i - 1) + (long) arr[i - 2] * i;
            dp[i] = Math.max(keep, swap);
        }
        return dp[n];
    }
}
long long getMaximumSumOfStrengths(vector<int>& arr) {
 int n = arr.size();
 if (n == 0) return 0;
 vector<long long> dp(n + 1, 0);
 dp[1] = (long long) arr[0] * 1;
 for (int i = 2; i <= n; i++) {
 long long keep = dp[i - 1] + (long long) arr[i - 1] * i;
 long long swap = dp[i - 2] + (long long) arr[i - 1] * (i - 1) + (long long) arr[i - 2] * i;
 dp[i] = max(keep, swap);
 }
 return dp[n];
}

Hudson River Trading

Hudson River Trading OA 真题，三语题解(Python / Java / C++)。

Optiver

Optiver OA 真题，三语题解(Python / Java / C++)。