Re: [閒聊] 每日LeetCode已回收
1626. Best Team With No Conflicts
每個球員有分數及年齡，要挑出一支球隊
其中年齡比較大的隊員的分數不能比較小
問總分最高多少
有點像權重版的 longest nondecreasing subsequence
不過寫一寫覺得比想像中麻煩，不太像是 Medium
寫完才發現 n <= 1000 所以其實 O(n^2) 就會過了
首先照年齡排好序後，對於第 i 個球員
在他之前都是年齡比他小的
所以要在那些分數比他小的球員裡選
也就是
DP[i] = max_j (DP[j] + scores[i]) where scores[j] <= scores[i]
到這裡 O(n^2) 的演算法已經可以很容易寫出來了
不過我們可以維護一個 ordered_map 從 score 對應到能得到的總分
並且保持若 a < b 則 map[a] < map[b]
這可以藉由每次插入時都移除那些不符合的人來維護
這樣對於 scores[i] 而言我們只要花 logn 找到在 map 裡
比他小的最大 key 就可以了
因為一個球員最多插入和移除一次
所以最後的複雜度還是 O(nlogn)
class Solution {
public:
int bestTeamScore(vector<int>& scores, vector<int>& ages) {
int n = scores.size();
using T = pair<int, int>;
vector<T> V(n);
for (int i = 0; i < n; i++)
V[i] = { ages[i], scores[i] };
sort(V.begin(), V.end());
map<int, int> M{{0, 0}}; // score -> total
for (auto [_, sc]: V) {
auto it = M.upper_bound(sc);
it--;
int total = sc + it->second;
vector<int> rm;
for (it++; it != M.end(); it++) {
if (total < it->second) break;
rm.push_back(it->first);
}
for (int r: rm) M.erase(r);
M[sc] = total;
}
return prev(M.end())->second;
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.175 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1675132165.A.97C.html
→
01/31 10:30,
2年前
, 1F
01/31 10:30, 1F
→
01/31 10:39,
2年前
, 2F
01/31 10:39, 2F
推
01/31 10:53,
2年前
, 3F
01/31 10:53, 3F
推
01/31 11:02,
2年前
, 4F
01/31 11:02, 4F
討論串 (同標題文章)
完整討論串 (本文為第 212 之 719 篇)：