Abaka.ai

01Task Scheduling (Parallel Same-Type with Memory Limit)

Given an array taskMemory of n positive integers representing memory required for each task, an array taskType of n positive integers representing task types, and an integer maxMemory, find the minimum time required to process all tasks.

Each task takes 1 unit of time. The server can process at most 2 tasks in parallel only if they are the same type and together require no more than maxMemory units.

Example: n=4, taskMemory=[7,2,3,9], taskType=[1,2,1,3], maxMemory=10 → 3. Group by type: type 1 = [7,3] pair under 10 → 1 unit; type 2 = [2] → 1 unit; type 3 = [9] → 1 unit; total 3.

Constraints

1 ≤ n ≤ 2×10⁵, 1 ≤ maxMemory, taskMemory[i] ≤ 10⁹, 1 ≤ taskType[i] ≤ 10⁹.

解法

按类型分桶，每组内排序后双指针配对(最小 + 最大)使其和 ≤ maxMemory。复杂度 O(N log N)。

from collections import defaultdict

def getMinTime(taskMemory, taskType, maxMemory):
    groups = defaultdict(list)
    for m, t in zip(taskMemory, taskType):
        groups[t].append(m)
    time = 0
    for arr in groups.values():
        arr.sort()
        l, r = 0, len(arr) - 1
        while l < r:
            if arr[l] + arr[r] <= maxMemory:
                time += 1
                l += 1
                r -= 1
            else:
                time += 1
                r -= 1
        if l == r:
            time += 1
    return time

class Solution {
    static long getMinTime(int[] mem, int[] type, int maxMem) {
        Map<Integer, List<Integer>> groups = new HashMap<>();
        for (int i = 0; i < mem.length; i++)
            groups.computeIfAbsent(type[i], k -> new ArrayList<>()).add(mem[i]);
        long time = 0;
        for (List<Integer> g : groups.values()) {
            Collections.sort(g);
            int l = 0, r = g.size() - 1;
            while (l < r) {
                if (g.get(l) + g.get(r) <= maxMem) { time++; l++; r--; }
                else { time++; r--; }
            }
            if (l == r) time++;
        }
        return time;
    }
}

long long getMinTime(vector<int>& mem, vector<int>& type, int maxMem) {
 unordered_map<int, vector<int>> groups;
 for (size_t i = 0; i < mem.size(); i++) groups[type[i]].push_back(mem[i]);
 long long time = 0;
 for (auto& [_, g] : groups) {
 sort(g.begin(), g.end());
 int l = 0, r = (int)g.size() - 1;
 while (l < r) {
 if (g[l] + g[r] <= maxMem) { time++; l++; r--; }
 else { time++; r--; }
 }
 if (l == r) time++;
 }
 return time;
}

02Maximize the Power

Given an array arr of n non-negative integers and an array power of k integers where k is an even number, perform the following operations:

Select two integers i and j such that 0 ≤ i < j < length of power. In each operation, i and j are selected independently.
If power[i] ≤ power[j], add the sum of the subarray arr[power[i] .. power[j]] to the power.
If power[i] > power[j], add the sum of the subarray arr[power[j] .. power[i]] to the power.
Delete the i-th and j-th elements from power, reducing its length by 2.

Starting with 0 initial power, maximize the final power after exactly k/2 operations. Return the maximum power possible modulo 10⁹+7.

Example: arr = [3, 5, 6, 0, 7], power = [3, 1, 0, 2], k = 4 → 25.

解法

对 power 排序，arr 做前缀和。贪心地把最小下标与最大下标配对(子数组和最大化)，每对的贡献是 pref[r+1] - pref[l]。复杂度 O(N + k log k)。

MOD = 10**9 + 7

def get_maximum_power(arr, power):
    n = len(arr)
    pref = [0] * (n + 1)
    for i in range(n):
        pref[i+1] = pref[i] + arr[i]
    p = sorted(power)
    k = len(p)
    ans = 0
    for i in range(k // 2):
        ans -= pref[p[i]]
        ans += pref[p[k-1-i] + 1]
    return ans % MOD

class Solution {
    static long getMaximumPower(int[] arr, int[] power) {
        long MOD = 1_000_000_007L;
        int n = arr.length;
        long[] pref = new long[n + 1];
        for (int i = 0; i < n; i++) pref[i + 1] = pref[i] + arr[i];
        int[] p = power.clone();
        Arrays.sort(p);
        int k = p.length;
        long ans = 0;
        for (int i = 0; i < k / 2; i++) {
            ans -= pref[p[i]];
            ans += pref[p[k - 1 - i] + 1];
        }
        return ((ans % MOD) + MOD) % MOD;
    }
}

long long getMaximumPower(vector<int>& arr, vector<int>& power) {
 const long long MOD = 1'000'000'007LL;
 int n = arr.size();
 vector<long long> pref(n + 1, 0);
 for (int i = 0; i < n; i++) pref[i + 1] = pref[i] + arr[i];
 vector<int> p = power;
 sort(p.begin(), p.end());
 int k = p.size();
 long long ans = 0;
 for (int i = 0; i < k / 2; i++) {
 ans -= pref[p[i]];
 ans += pref[p[k - 1 - i] + 1];
 }
 return ((ans % MOD) + MOD) % MOD;
}