In our system, we have a pipeline consisting of data processing units, each with varying throughputs as represented by throughput[i]. These units are arranged in a series, requiring data to pass through each of them sequentially. Consequently, the total throughput of the pipeline is constrained by the unit with the smallest throughput, which becomes the bottleneck.
Each service can be scaled up independently, with the cost of scaling up the i-th service one unit equal to scaling_cost[i]. After scaling up a service x times, it can process throughput[i] × (1 + x) messages per minute.
Given arrays throughput[n], scaling_cost[n], integer budget, and integer n, determine the optimal scaling configuration so that the throughput generated by the n-th service is maximized. Return that max throughput.
Example: throughput = [4,2,7], scaling_cost = [3,5,6], budget = 32 → 10.
解法
对答案 T 二分：吞吐 T 可行当且仅当 sum((ceil(T/tp[i]) - 1) * sc[i]) ≤ budget。搜索区间 [min(tp), max(tp) * (budget/min_cost + 1)]。复杂度 O(n log(max_T))。
def get_maximum_throughput(tp, sc, budget, n):
lo, hi, min_cost = min(tp), max(tp), min(sc)
hi = hi * (budget // min_cost + 1) + 1
def feasible(T):
cost = 0
for i in range(n):
need = max(0, (T + tp[i] - 1) // tp[i] - 1)
cost += sc[i] * need
if cost > budget:
return False
return True
while lo < hi:
mid = lo + (hi - lo + 1) // 2
if feasible(mid):
lo = mid
else:
hi = mid - 1
return loclass Solution {
static long getMaximumThroughput(int[] tp, int[] sc, long budget, int n) {
long lo = Long.MAX_VALUE, hi = 0, minCost = Long.MAX_VALUE;
for (int i = 0; i < n; i++) {
lo = Math.min(lo, tp[i]);
hi = Math.max(hi, tp[i]);
minCost = Math.min(minCost, sc[i]);
}
hi = hi * (budget / minCost + 1) + 1;
while (lo < hi) {
long mid = lo + (hi - lo + 1) / 2;
if (feasible(tp, sc, n, mid, budget)) lo = mid;
else hi = mid - 1;
}
return lo;
}
static boolean feasible(int[] tp, int[] sc, int n, long T, long budget) {
long cost = 0;
for (int i = 0; i < n; i++) {
long need = Math.max(0, (T + tp[i] - 1) / tp[i] - 1);
cost += (long) sc[i] * need;
if (cost > budget) return false;
}
return true;
}
}bool feasible(vector<int>& tp, vector<int>& sc, int n, long long T, long long budget) {
long long cost = 0;
for (int i = 0; i < n; i++) {
long long need = max(0LL, (T + tp[i] - 1) / tp[i] - 1);
cost += (long long)sc[i] * need;
if (cost > budget) return false;
}
return true;
}
long long getMaximumThroughput(vector<int>& tp, vector<int>& sc, long long budget, int n) {
long long lo = *min_element(tp.begin(), tp.end());
long long hi = *max_element(tp.begin(), tp.end());
long long minCost = *min_element(sc.begin(), sc.end());
hi = hi * (budget / minCost + 1) + 1;
while (lo < hi) {
long long mid = lo + (hi - lo + 1) / 2;
if (feasible(tp, sc, n, mid, budget)) lo = mid;
else hi = mid - 1;
}
return lo;
}The agency is giving you an int num named N and an arr of ints called arr[n]. Ur task -
-
- Find two nums with indices a & b (where b > a)
-
- Figure out the toal of the two nums
-
- Make sure the total is divisible by N
- Finally, return the number of special pairs that meet the criteria outlined in tasks 1 through 3
Constraints
1 ≤ N ≤ 10⁹1 ≤ len of arr ≤ 10⁵1 ≤ arr[i] ≤ 10⁹
Example 1
Input:
N = 3
arr = [5, 4, 3, 2, 1]Output:
4Explanation: We can that there are FOUR pairs that meet the criteria outlined in task 1 through task 3 above arr[0] + arr[1] = 1 + 2 = 3, 3 3 = 1 arr[0] + arr[4] = 1 + 5 = 6, 6 3 = 2 arr[1] + arr[3] = 2 + 4 = 6, 6 3 = 2 arr[3] + arr[4] = 4 + 5 = 9, 9 3 = 3 So, 4 should be returned. For original prompt, pls refer source image.
解法
用计数：对每个 r ∈ [0, N) 统计 arr[i] % N == r 的个数。配对 (a, b) 满足 (arr[a] + arr[b]) % N == 0 ⇔ arr[b] % N == (N - arr[a] % N) % N。r == 0 自配对 C(cnt[0], 2)；其它 r ≠ N/2：cnt[r] * cnt[N-r]；r == N/2(N 偶数)：C(cnt[N/2], 2)。注意只配对一次。复杂度 O(n)。
from typing import List
from collections import Counter
def nums_that_can_be_divided_by_n(N: int, arr: List[int]) -> int:
mod_cnt = Counter(x % N for x in arr)
total = 0
keys = list(mod_cnt.keys())
for r in mod_cnt:
if r == 0:
c = mod_cnt[r]
total += c * (c - 1) // 2
elif 2 * r == N:
c = mod_cnt[r]
total += c * (c - 1) // 2
elif r < N - r:
total += mod_cnt[r] * mod_cnt.get(N - r, 0)
return totalimport java.util.*;
class Solution {
long numsThatCanBeDividedByN(int N, int[] arr) {
long[] mod = new long[N];
for (int x : arr) mod[x % N]++;
long total = 0;
for (int r = 0; r < N; r++) {
if (r == 0 || 2 * r == N) total += mod[r] * (mod[r] - 1) / 2;
else if (r < N - r) total += mod[r] * mod[N - r];
}
return total;
}
}class Solution {
public:
long long numsThatCanBeDividedByN(int N, vector<int>& arr) {
vector<long long> mod(N, 0);
for (int x : arr) mod[x % N]++;
long long total = 0;
for (int r = 0; r < N; r++) {
if (r == 0 || 2 * r == N) total += mod[r] * (mod[r] - 1) / 2;
else if (r < N - r) total += mod[r] * mod[N - r];
}
return total;
}
};Sup ! This time the agency will give you:
- An int 2D arr
- A position within the input 2D arr
- A so called replacing val What they want you to do: Replace the val at the starting position with the provided replacing val. Repeat this process for all positions connected to the starting position via sides with the same val as the starting position.
Constraints
1 ≤ arr.length, arr[0].length ≤ 10000 ≤ arr[i][j] ≤ 10^90 ≤ pos[0] < arr.length，0 ≤ pos[1] < arr[0].length0 ≤ replacingVal ≤ 10^9
Example 1
Input:
replacingVal = 2
arr = [[0, 1, 0, 0, 0], [1, 1, 1, 0, 0], [1, 1, 0, 0, 0], [0, 1, 0, 1, 0]]
pos = [1, 2]Output:
[[0, 2, 0, 0, 0], [2, 2, 2, 0, 0], [2, 2, 0, 0, 0], [0, 2, 0, 1, 0]]Explanation: No explanation is provided for now. For original prompt, pls refer source image.
解法
经典 floodfill：BFS / DFS 从起点向 4 邻居扩散，把相同原值的位置替换为新值。若新值等于原值直接返回。复杂度 O(rows · cols)。
from typing import List
from collections import deque
def replacing_num(replacingVal: int, arr: List[List[int]], pos: List[int]) -> List[List[int]]:
if not arr or not arr[0]:
return arr
r0, c0 = pos
old = arr[r0][c0]
if old == replacingVal:
return arr
rows, cols = len(arr), len(arr[0])
q = deque([(r0, c0)])
arr[r0][c0] = replacingVal
while q:
r, c = q.popleft()
for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and arr[nr][nc] == old:
arr[nr][nc] = replacingVal
q.append((nr, nc))
return arrimport java.util.*;
class Solution {
int[][] replacingNum(int replacingVal, int[][] arr, int[] pos) {
if (arr.length == 0) return arr;
int r0 = pos[0], c0 = pos[1];
int old = arr[r0][c0];
if (old == replacingVal) return arr;
int rows = arr.length, cols = arr[0].length;
Deque<int[]> q = new ArrayDeque<>();
q.add(new int[]{r0, c0});
arr[r0][c0] = replacingVal;
int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
while (!q.isEmpty()) {
int[] cur = q.poll();
for (int[] d : dirs) {
int nr = cur[0] + d[0], nc = cur[1] + d[1];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && arr[nr][nc] == old) {
arr[nr][nc] = replacingVal;
q.add(new int[]{nr, nc});
}
}
}
return arr;
}
}class Solution {
public:
vector<vector<int>> replacingNum(int replacingVal, vector<vector<int>> arr, vector<int> pos) {
if (arr.empty()) return arr;
int r0 = pos[0], c0 = pos[1];
int old = arr[r0][c0];
if (old == replacingVal) return arr;
int rows = arr.size(), cols = arr[0].size();
queue<pair<int, int>> q;
q.push({r0, c0});
arr[r0][c0] = replacingVal;
int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
while (!q.empty()) {
auto [r, c] = q.front(); q.pop();
for (auto& d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && arr[nr][nc] == old) {
arr[nr][nc] = replacingVal;
q.push({nr, nc});
}
}
}
return arr;
}
};