$
Example 1
Input:
cost = [10, 20, 14, 40, 50]
x = 70Output:
20Explanation:
- Items 0, 1, and 2 for a cost of 44 and obtain a profit of 2 ** 0 + 2 ** 1 + 2 ** 2 = 7
- Items 0 and 4 for a cost of 60 and obtain a profit of 2 ** 0 + 2 ** 4 = 17
- Items 1 and 4 for a cost of 70 and obtain a profit of 2 ** 1 + 2 ** 4 = 18
- Items 2 and 4 for a cost of 64 and obtain a profit of 2 ** 2 + 2 ** 4 = 20 Out of all the possible combinations, the maximum profit is 20 when purchasing items 2 and 4 for a cost of 64.
解法
每个物品 i 选不选；选了利润 += 2^i，成本 += cost[i]，预算 ≤ x。要最大化 Σ 2^i，等价于"在不超预算下选下标集合使位掩码值最大"。从高位(最大 i)开始贪心：若选 cost[i] ≤ 剩余预算 则选。证明：2^i > 2⁰ + ... + 2^{i-1}，所以高位优先严格更优。时间 O(n)。
from typing import List
def calculate_max_profit(cost: List[int], x: int) -> int:
profit = 0
budget = x
for i in range(len(cost) - 1, -1, -1):
if cost[i] <= budget:
budget -= cost[i]
profit += 1 << i
return profitclass Solution {
public long calculateMaxProfit(int[] cost, int x) {
long profit = 0, budget = x;
for (int i = cost.length - 1; i >= 0; i--) {
if (cost[i] <= budget) { budget -= cost[i]; profit += 1L << i; }
}
return profit;
}
}#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
long long calculateMaxProfit(vector<int>& cost, int x) {
long long profit = 0, budget = x;
for (int i = (int)cost.size() - 1; i >= 0; i--) {
if (cost[i] <= budget) { budget -= cost[i]; profit += 1LL << i; }
}
return profit;
}
};In a distributed network system, data packets with unique identifiers and checksum values are sent between nodes to maintain communication and data integrity. Develop a function to aggregate the checksum values for all possible pairs of packets within the network.
For any two distinct packets with identifiers i and j, the checksum is calculated as C(i, j) = i mod j + j mod i. Calculate the sum of C(i, j) for all pairs (1 Function Description Complete the function computeChecksumAggregationin the editor.computeChecksumAggregation` has the following parameter:
int n: the total number of packets in the network Returnsint: the aggregated checksum
Constraints
1 ≤ n ≤ 10 ** 6
解法
求 Σ over pairs (i mod j + j mod i)。注意 i < j 时 i mod j = i。所以 Σ (i mod j) over all pairs = Σ_j j*(j-1)/2 = n*(n-1)*(n+1)/6。Σ (j mod i) 需要逐 i 累加：对每个 i，j 从 i+1 到 n，j mod i 的和可对 i 用分块：每个完整周期 [k*i, k*i+i-1] 贡献 i*(i-1)/2，再加最后不完整段。整体 O(n log n)。最后取 mod。
MOD = 10 ** 9 + 7
def compute_checksum_aggregation(n: int) -> int:
# Σ (i mod j) for i<j: i mod j = i; total = Σ_j Σ_{i=1}^{j-1} i = Σ_j j(j-1)/2 = n(n-1)(n+1)/6
part1 = n * (n - 1) % MOD * ((n + 1) % MOD) % MOD * pow(6, MOD - 2, MOD) % MOD
# Σ (j mod i) over all pairs i<j:
part2 = 0
for i in range(1, n + 1):
# j from i+1 to n: j mod i
# let total j in [i+1, n] = n - i. Number of full periods = (n - i) // i? Need careful.
# j ranges i+1..n. j mod i cycles every i.
full_blocks = (n - i + 1) // i # blocks of i values: [i, 2i-1], [2i, 3i-1], ...
# The first j is i, last j is n. j mod i ranges (i..n).
# Easier: total Σ_{j=i+1}^{n} (j mod i)
s = 0
m_first = i + 1
m_last = n
# For j in [a, b], Σ (j mod i):
# Express j = q*i + r, r in [0, i-1]. As j increases by 1, r cycles.
block_sum = i * (i - 1) // 2
full = (m_last - m_first + 1) // i
# but offset matters. Simpler: iterate r-cycle starting at (m_first % i)
start_r = m_first % i
# Number of full cycles from start_r
s += block_sum * full
# Remaining
rem = (m_last - m_first + 1) - full * i
r = start_r
for _ in range(rem):
s += r
r = (r + 1) % i
part2 = (part2 + s) % MOD
return (part1 + part2) % MODclass Solution {
static final long MOD = 1_000_000_007L;
public long computeChecksumAggregation(int n) {
long part1 = (long) n * (n - 1) % MOD * ((n + 1) % MOD) % MOD * modpow(6, MOD - 2, MOD) % MOD;
long part2 = 0;
for (int i = 1; i <= n; i++) {
int mFirst = i + 1, mLast = n;
if (mFirst > mLast) continue;
long blockSum = (long) i * (i - 1) / 2;
int len = mLast - mFirst + 1;
int full = len / i;
long s = blockSum * full;
int startR = mFirst % i;
int rem = len - full * i;
int r = startR;
for (int t = 0; t < rem; t++) { s += r; r = (r + 1) % i; }
part2 = (part2 + s % MOD) % MOD;
}
return (part1 + part2) % MOD;
}
long modpow(long b, long e, long m) { long r = 1; b %= m; while (e > 0) { if ((e & 1) == 1) r = r * b % m; b = b * b % m; e >>= 1; } return r; }
}#include <bits/stdc++.h>
using namespace std;
class Solution {
static constexpr long long MOD = 1000000007;
long long modpow(long long b, long long e, long long m) { long long r = 1; b %= m; while (e) { if (e & 1) r = r * b % m; b = b * b % m; e >>= 1; } return r; }
public:
int computeChecksumAggregation(int n) {
long long part1 = (long long)n * (n - 1) % MOD * ((n + 1) % MOD) % MOD * modpow(6, MOD - 2, MOD) % MOD;
long long part2 = 0;
for (int i = 1; i <= n; i++) {
int mFirst = i + 1, mLast = n;
if (mFirst > mLast) continue;
long long blockSum = (long long)i * (i - 1) / 2;
int len = mLast - mFirst + 1;
int full = len / i;
long long s = blockSum * full;
int startR = mFirst % i;
int rem = len - full * i;
int r = startR;
for (int t = 0; t < rem; t++) { s += r; r = (r + 1) % i; }
part2 = (part2 + s % MOD) % MOD;
}
return (int)((part1 + part2) % MOD);
}
};In a k-means clustering problem, a dataset contains n data points, where i data point is represented by the feature vector location[i]. The goal is to create k clusters. where the cluster centers or the cluster centroids can be placed at any point in the feature space. The overall quality of the clustering is measured by the maximum distance between any data point and its nearest cluster center.
The best possible quality is achieved by optimally placing the cluster centers to minimize this maximum distance. Determine this maximum distance between any data point and its nearest cluster center.
Note: The distance between two feature points x and y is defined as |x - y|, where |x| denotes the absolute value of x.
My deepest and boundless gratitude to the incredible friend who so kindly shared this resource!
Example 1
Input:
location = [4, 1, 6, 7, 2]
k = 2Output:
2Explanation:
解法
同 atlassian get-maximum-distance：把 location 排序，二分答案 d，贪心检查最少需要多少簇(每簇最多覆盖直径 2d)。时间 O(n log V)。
from typing import List
def get_maximum_distance(location: List[int], k: int) -> int:
loc = sorted(location)
n = len(loc)
if k >= n:
return 0
def can(d: int) -> bool:
clusters = 1
a = loc[0]
for x in loc:
if x - a > 2 * d:
clusters += 1
a = x
if clusters > k:
return False
return True
lo, hi = 0, (loc[-1] - loc[0] + 1) // 2 + 1
while lo < hi:
mid = (lo + hi) // 2
if can(mid): hi = mid
else: lo = mid + 1
return loimport java.util.*;
class Solution {
public int getMaximumDistance(int[] location, int k) {
int[] loc = location.clone();
Arrays.sort(loc);
int n = loc.length;
if (k >= n) return 0;
int lo = 0, hi = (loc[n - 1] - loc[0] + 1) / 2 + 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
int clusters = 1, a = loc[0];
boolean ok = true;
for (int x : loc) if (x - a > 2L * mid) { clusters++; a = x; if (clusters > k) { ok = false; break; } }
if (ok) hi = mid; else lo = mid + 1;
}
return lo;
}
}#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int getMaximumDistance(vector<int>& location, int k) {
vector<int> loc = location;
sort(loc.begin(), loc.end());
int n = loc.size();
if (k >= n) return 0;
int lo = 0, hi = (loc.back() - loc.front() + 1) / 2 + 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
int clusters = 1, a = loc[0];
bool ok = true;
for (int x : loc) if (x - a > 2 * mid) { clusters++; a = x; if (clusters > k) { ok = false; break; } }
if (ok) hi = mid; else lo = mid + 1;
}
return lo;
}
};