You work for a pharmaceutical company that produces liquid medicines. Patients requiring these medications often require different amounts. To package the medication for delivery, you can choose between different sets of containers. Each container set specifies the sizes of containers it allows. For example, set 1 might contain containers with size 200 ml and 300 ml, while set 2 might use containers with size 400 ml, 300 ml and 100 ml.
When fulfilling a customer order for a given amount, a single container must be used and filled completely. If a container does not exist that matches the required amount, the next largest container is used. The extra medication included in that larger container (i.e., the size of the container minus required amount) is considered waste.
Your job is to evaluate different sets of containers and find the set that creates the minimum amount of waste over a set of orders. Return the 1-based index of the optimal container set. In case of a tie, return the lowest-indexed set.
Example
requirements = [10, 15]
containers = [
[5, 30, 20, 10],
[10, 5, 15, 20, 30],
]
Set 0: order 10 -> 10 (waste 0); order 15 -> 20 (waste 5). Total 5.
Set 1: order 10 -> 10 (waste 0); order 15 -> 15 (waste 0). Total 0.
Answer: 2 (1-based).解法
每个 set 排序；对每个订单二分找 ≥ 需求的最小容器，找不到则跳过该 set；累加每个 set 的浪费，取最小。复杂度 O(S * (C log C + R log C))。
import bisect
def minWasteSet(requirements, containersList):
best_idx, best_waste = -1, float('inf')
for idx, containers in enumerate(containersList, start=1):
sc = sorted(containers)
waste = 0
ok = True
for r in requirements:
pos = bisect.bisect_left(sc, r)
if pos == len(sc):
ok = False
break
waste += sc[pos] - r
if ok and waste < best_waste:
best_waste = waste
best_idx = idx
return best_idximport java.util.*;
class Solution {
static int minWasteSet(int[] req, int[][] sets) {
int bestIdx = -1;
long bestWaste = Long.MAX_VALUE;
for (int s = 0; s < sets.length; s++) {
int[] sc = sets[s].clone();
Arrays.sort(sc);
long waste = 0;
boolean ok = true;
for (int r : req) {
int lo = 0, hi = sc.length;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (sc[mid] < r) lo = mid + 1; else hi = mid;
}
if (lo == sc.length) { ok = false; break; }
waste += sc[lo] - r;
}
if (ok && waste < bestWaste) { bestWaste = waste; bestIdx = s + 1; }
}
return bestIdx;
}
}#include <bits/stdc++.h>
using namespace std;
int minWasteSet(vector<int>& requirements, vector<vector<int>>& containersList) {
int bestIdx = -1;
long long bestWaste = LLONG_MAX;
for (int s = 0; s < (int) containersList.size(); s++) {
vector<int> sc = containersList[s];
sort(sc.begin(), sc.end());
long long waste = 0;
bool ok = true;
for (int r : requirements) {
auto it = lower_bound(sc.begin(), sc.end(), r);
if (it == sc.end()) { ok = false; break; }
waste += *it - r;
}
if (ok && waste < bestWaste) { bestWaste = waste; bestIdx = s + 1; }
}
return bestIdx;
}An organization is made up of n people. The hierarchy is represented as a tree where parent[i] is the parent of node i; parent[0] = -1 is the root.
A directive issued from person p propagates this way:
- The issuer sends the directive to direct children in ascending order of indices.
- For each child, the directive fully propagates through that child's subtree before moving to the next child.
- Each child node propagates to its own children the same way.
For each query (p, k), return the k-th person to receive the directive starting from p (1-indexed counting the issuer as position 1). If fewer than k people exist in p's subtree, return -1.
Example: n=9, parent=[-1, 0, 0, 1, 1, 1, 2, 6, 7], queries=[(0, 4), (1, 3), (5, 1), (6, 2)] -> [5, 5, 6, 8].
解法
DFS 整棵树(孩子按升序)，记录欧拉序的 enter[u] 和 leave[u]。在 p 子树内第 k 个节点就是 tour[enter[p] + k - 1]，需保证下标 ≤ leave[p]。复杂度 O(n + q)。
def chainOfCommand(n, parent, queries):
from collections import defaultdict
children = defaultdict(list)
root = 0
for i, p in enumerate(parent):
if p == -1:
root = i
else:
children[p].append(i)
for p in children:
children[p].sort()
enter, leave = [0] * n, [0] * n
tour = []
def dfs(u):
enter[u] = len(tour)
tour.append(u)
for c in children[u]:
dfs(c)
leave[u] = len(tour) - 1
dfs(root)
out = []
for p, k in queries:
idx = enter[p] + k - 1
if idx > leave[p]:
out.append(-1)
else:
out.append(tour[idx])
return outimport java.util.*;
class Solution {
int[] enter, leave;
List<Integer> tour;
List<List<Integer>> children;
void dfs(int u) {
enter[u] = tour.size();
tour.add(u);
for (int c : children.get(u)) dfs(c);
leave[u] = tour.size() - 1;
}
int[] chainOfCommand(int n, int[] parent, int[][] queries) {
children = new ArrayList<>();
for (int i = 0; i < n; i++) children.add(new ArrayList<>());
int root = 0;
for (int i = 0; i < n; i++) {
if (parent[i] == -1) root = i;
else children.get(parent[i]).add(i);
}
for (List<Integer> l : children) Collections.sort(l);
enter = new int[n];
leave = new int[n];
tour = new ArrayList<>();
dfs(root);
int[] out = new int[queries.length];
for (int q = 0; q < queries.length; q++) {
int p = queries[q][0], k = queries[q][1];
int idx = enter[p] + k - 1;
out[q] = (idx > leave[p]) ? -1 : tour.get(idx);
}
return out;
}
}#include <bits/stdc++.h>
using namespace std;
class Solution {
vector<int> enter_, leave_, tour;
vector<vector<int>> children;
void dfs(int u) {
enter_[u] = tour.size();
tour.push_back(u);
for (int c : children[u]) dfs(c);
leave_[u] = tour.size() - 1;
}
public:
vector<int> chainOfCommand(int n, vector<int>& parent, vector<pair<int,int>>& queries) {
children.assign(n, {});
int root = 0;
for (int i = 0; i < n; i++) {
if (parent[i] == -1) root = i;
else children[parent[i]].push_back(i);
}
for (auto& l : children) sort(l.begin(), l.end());
enter_.assign(n, 0);
leave_.assign(n, 0);
tour.clear();
dfs(root);
vector<int> out;
for (auto& [p, k] : queries) {
int idx = enter_[p] + k - 1;
out.push_back(idx > leave_[p] ? -1 : tour[idx]);
}
return out;
}
};In this game, there are a number asteroids arranged in line. These asteroids can all move either left or right on the line and all asteroids move at the same speed. Each asteroid also has a size associated with it. If two asteroids that are next to each other move towards each other, they will collide. In this case, the larger asteroid will destroy the smaller one. If both asteroids have the same size, then both asteroids are destroyed. The purpose of this game is to determine which asteroids remain after all possible collisions occur.
Thus, given an array size of length n, where size[i] is the size of the i^th asteroid and a second array direction of size n where direction[i] is the direction of the i^thasteroid where 0 indicates moving left and 1 indicates moving right.
Given these inputs, find which asteroids remain after all collisions have taken place. Return an array containing the sizes of the remaining asteroids (in order). If no asteroids remain, then return an empty array.
Constraints
A mysterious secrete for now
Example 1
Input:
size = [4, 5, 6, 7, 4]
direction = [1, 1, 1, 0, 1, 0]Output:
[6, 7]Explanation: A direction value if 1 indicates moving to the right and a direction value of 0 indicates moving to the left. Collisions:
- size[1], size[2]: 5 4 so size[4] vanishes and there are no more asteroids to the right of size[4] Only size[2] and size[3] remain. Return them in the order they appear in size [6, 7].
Example 2
Input:
size = [3, 4, 2, 1, 6, 4, 5]
direction = [1, 0, 1, 0, 1, 1, 0]Output:
[4, 2, 6]Explanation: The initial size array = [3, 4, 2, 1, 6, 4, 5] with direction = [1, 0, 1, 0, 1, 1, 0] The collisions are between asteroids with sizes:
- (3, 4) 4 remains
- (2, 1) 2 remains
- (4, 5) 5 remains (no more collision to go)
- (6, 5) 6 remains The remaining asteroids are [4, 2, 6].
Example 3
Input:
size = [5, 5]
direction = [1, 0]Output:
[]Explanation: The initial size array = [5, -5] with direction = [1, 0] The first and second asteroids collide. Since they are of the same size, both of them disappear .
解法
单调栈模拟。把 direction == 1 视为正向(右行)，direction == 0 视为反向(左行)。维护栈：遇到右行直接入栈；遇到左行则不断与栈顶右行碰撞(若栈顶 < 当前，弹出栈顶继续；等于则两者都消失；大于则当前消失)，否则入栈。复杂度 O(n)。
from typing import List
def asteroid_game(size: List[int], direction: List[int]) -> List[int]:
stk = []
for s, d in zip(size, direction):
alive = True
while alive and d == 0 and stk and stk[-1][1] == 1:
top_s, _ = stk[-1]
if top_s < s:
stk.pop()
elif top_s == s:
stk.pop()
alive = False
else:
alive = False
if alive:
stk.append((s, d))
return [s for s, _ in stk]import java.util.*;
class Solution {
int[] asteroidGame(int[] size, int[] direction) {
Deque<int[]> stk = new ArrayDeque<>();
for (int i = 0; i < size.length; i++) {
int s = size[i], d = direction[i];
boolean alive = true;
while (alive && d == 0 && !stk.isEmpty() && stk.peek()[1] == 1) {
int[] top = stk.peek();
if (top[0] < s) stk.pop();
else if (top[0] == s) { stk.pop(); alive = false; }
else alive = false;
}
if (alive) stk.push(new int[]{s, d});
}
int[] res = new int[stk.size()];
int idx = res.length - 1;
for (int[] a : stk) res[idx--] = a[0];
return res;
}
}class Solution {
public:
vector<int> asteroidGame(vector<int>& size, vector<int>& direction) {
vector<pair<int, int>> stk;
for (size_t i = 0; i < size.size(); ++i) {
int s = size[i], d = direction[i];
bool alive = true;
while (alive && d == 0 && !stk.empty() && stk.back().second == 1) {
if (stk.back().first < s) stk.pop_back();
else if (stk.back().first == s) { stk.pop_back(); alive = false; }
else alive = false;
}
if (alive) stk.push_back({s, d});
}
vector<int> res;
for (auto& p : stk) res.push_back(p.first);
return res;
}
};