class Solution {
public:
long long findMaximumElegance(vector<vector<int>>& items, int k) {
}
};
6932. 子序列最大优雅度
给你一个长度为 n 的二维整数数组 items 和一个整数 k 。
items[i] = [profiti, categoryi]，其中 profiti 和 categoryi 分别表示第 i 个项目的利润和类别。
现定义 items 的 子序列 的 优雅度 可以用 total_profit + distinct_categories2 计算，其中 total_profit 是子序列中所有项目的利润总和，distinct_categories 是所选子序列所含的所有类别中不同类别的数量。
你的任务是从 items 所有长度为 k 的子序列中，找出 最大优雅度 。
用整数形式表示并返回 items 中所有长度恰好为 k 的子序列的最大优雅度。
注意：数组的子序列是经由原数组删除一些元素（可能不删除）而产生的新数组，且删除不改变其余元素相对顺序。
示例 1：
输入：items = [[3,2],[5,1],[10,1]], k = 2 输出：17 解释： 在这个例子中，我们需要选出长度为 2 的子序列。 其中一种方案是 items[0] = [3,2] 和 items[2] = [10,1] 。 子序列的总利润为 3 + 10 = 13 ，子序列包含 2 种不同类别 [2,1] 。 因此，优雅度为 13 + 22 = 17 ，可以证明 17 是可以获得的最大优雅度。
示例 2：
输入：items = [[3,1],[3,1],[2,2],[5,3]], k = 3 输出：19 解释： 在这个例子中，我们需要选出长度为 3 的子序列。 其中一种方案是 items[0] = [3,1] ，items[2] = [2,2] 和 items[3] = [5,3] 。 子序列的总利润为 3 + 2 + 5 = 10 ，子序列包含 3 种不同类别 [1, 2, 3] 。 因此，优雅度为 10 + 32 = 19 ，可以证明 19 是可以获得的最大优雅度。
示例 3：
输入：items = [[1,1],[2,1],[3,1]], k = 3 输出：7 解释： 在这个例子中，我们需要选出长度为 3 的子序列。 我们需要选中所有项目。 子序列的总利润为 1 + 2 + 3 = 6，子序列包含 1 种不同类别 [1] 。 因此，最大优雅度为 6 + 12 = 7 。
提示：
1 <= items.length == n <= 105items[i].length == 2items[i][0] == profitiitems[i][1] == categoryi1 <= profiti <= 1091 <= categoryi <= n 1 <= k <= n原站题解
javascript 解法, 执行用时: 243 ms, 内存消耗: 73.9 MB, 提交时间: 2024-06-13 07:42:08
/**
* @param {number[][]} items
* @param {number} k
* @return {number}
*/
var findMaximumElegance = function(items, k) {
items.sort((item0, item1) => item1[0] - item0[0])
let categorySet = new Set();
let profit = 0, res = 0;
let st = [];
for (let i = 0; i < items.length; i++) {
if (i < k) {
profit += items[i][0];
if (!categorySet.has(items[i][1])) {
categorySet.add(items[i][1]);
} else {
st.push(items[i][0]);
}
} else if (st.length > 0 && !categorySet.has(items[i][1])) {
profit += items[i][0] - st.pop();
categorySet.add(items[i][1]);
}
res = Math.max(res, profit + categorySet.size * categorySet.size);
}
return res;
};
rust 解法, 执行用时: 58 ms, 内存消耗: 9.5 MB, 提交时间: 2024-06-13 07:41:54
use std::collections::{HashSet, VecDeque};
impl Solution {
pub fn find_maximum_elegance(mut items: Vec<Vec<i32>>, k: i32) -> i64 {
items.sort_unstable_by_key(|item| -item[0]);
let (mut categorySet, mut st) = (HashSet::new(), VecDeque::new());
let (mut res, mut profit) = (0 as i64, 0 as i64);
for (i, item) in items.iter().enumerate() {
if i < k as usize {
profit += item[0] as i64;
if !categorySet.contains(&item[1]) {
categorySet.insert(item[1]);
} else {
st.push_back(item[0]);
}
} else if (!categorySet.contains(&item[1]) && !st.is_empty()) {
profit += (item[0] - st.back().unwrap()) as i64;
st.pop_back();
categorySet.insert(item[1]);
}
res = res.max(profit + (categorySet.len() * categorySet.len()) as i64);
}
res as i64
}
}
golang 解法, 执行用时: 372 ms, 内存消耗: 17.7 MB, 提交时间: 2023-08-07 15:53:54
func findMaximumElegance(items [][]int, k int) int64 {
// 把利润从大到小排序
sort.Slice(items, func(i, j int) bool { return items[i][0] > items[j][0] })
ans, totalProfit := 0, 0
vis := map[int]bool{}
duplicate := []int{} // 重复类别的利润
for i, p := range items {
profit, category := p[0], p[1]
if i < k {
totalProfit += profit
if !vis[category] {
vis[category] = true
} else { // 重复类别
duplicate = append(duplicate, profit)
}
} else if len(duplicate) > 0 && !vis[category] {
vis[category] = true
totalProfit += profit - duplicate[len(duplicate)-1] // 选一个重复类别中的最小利润替换
duplicate = duplicate[:len(duplicate)-1]
} // else 比前面的利润小，而且类别还重复了，选它只会让 totalProfit 变小，len(vis) 不变，优雅度不会变大
ans = max(ans, totalProfit+len(vis)*len(vis))
}
return int64(ans)
}
func max(a, b int) int { if b > a { return b }; return a }
cpp 解法, 执行用时: 556 ms, 内存消耗: 177.3 MB, 提交时间: 2023-08-07 15:53:34
class Solution {
public:
long long findMaximumElegance(vector<vector<int>> &items, int k) {
// 把利润从大到小排序
sort(items.begin(), items.end(), [](const auto &a, const auto &b) {
return a[0] > b[0];
});
long long ans = 0, total_profit = 0;
unordered_set<int> vis;
stack<int> duplicate; // 重复类别的利润
for (int i = 0; i < items.size(); i++) {
int profit = items[i][0], category = items[i][1];
if (i < k) {
total_profit += profit;
if (!vis.insert(category).second) // 重复类别
duplicate.push(profit);
} else if (!duplicate.empty() && vis.insert(category).second) {
total_profit += profit - duplicate.top(); // 选一个重复类别中的最小利润替换
duplicate.pop();
} // else：比前面的利润小，而且类别还重复了，选它只会让 totalProfit 变小，vis.size() 不变，优雅度不会变大
ans = max(ans, total_profit + (long long) vis.size() * (long long) vis.size());
}
return ans;
}
};
java 解法, 执行用时: 51 ms, 内存消耗: 78.3 MB, 提交时间: 2023-08-07 15:53:14
class Solution {
public long findMaximumElegance(int[][] items, int k) {
// 把利润从大到小排序
Arrays.sort(items, (a, b) -> b[0] - a[0]);
long ans = 0, totalProfit = 0;
var vis = new HashSet<Integer>();
var duplicate = new ArrayDeque<Integer>(); // 重复类别的利润
for (int i = 0; i < items.length; i++) {
int profit = items[i][0], category = items[i][1];
if (i < k) {
totalProfit += profit;
if (!vis.add(category)) // 重复类别
duplicate.push(profit);
} else if (!duplicate.isEmpty() && vis.add(category)) {
totalProfit += profit - duplicate.pop(); // 选一个重复类别中的最小利润替换
} // else：比前面的利润小，而且类别还重复了，选它只会让 totalProfit 变小，vis.size() 不变，优雅度不会变大
ans = Math.max(ans, totalProfit + (long) vis.size() * vis.size()); // 注意 1e5*1e5 会溢出
}
return ans;
}
}
python3 解法, 执行用时: 248 ms, 内存消耗: 41.5 MB, 提交时间: 2023-08-07 15:52:53
'''
反悔贪心
'''
class Solution:
def findMaximumElegance(self, items: List[List[int]], k: int) -> int:
items.sort(key=lambda i: -i[0]) # 把利润从大到小排序
ans = total_profit = 0
vis = set()
duplicate = [] # 重复类别的利润
for i, (profit, category) in enumerate(items):
if i < k:
total_profit += profit
if category not in vis:
vis.add(category)
else: # 重复类别
duplicate.append(profit)
elif duplicate and category not in vis:
vis.add(category)
total_profit += profit - duplicate.pop() # 用最小利润替换
# else: 比前面的利润小，而且类别还重复了，选它只会让 total_profit 变小，len(vis) 不变，优雅度不会变大
ans = max(ans, total_profit + len(vis) * len(vis))
return ans
python3 解法, 执行用时: 324 ms, 内存消耗: 42.4 MB, 提交时间: 2023-08-07 15:52:03
'''
简单贪心
枚举答案包含的类别数 i。在 i 固定后，不妨贪心选取最大的 i 个类别不同的项目，
将他们代表的 i 种类别记为集合 B。然后从剩下的项目中选取最大的 k−i 个，记为集合 C。
注意 C 中可能有类别不在 B 中的项目，导致实际类别数 >i，但这没有关系，因为这时我们低估了答案。
'''
class Solution:
def findMaximumElegance(self, items: List[List[int]], k: int) -> int:
a = sorted([[x[1],x[0]] for x in items])[::-1]
n = len(a); b=[]; c=[]
for i, (x, y) in enumerate(a):
if i==0 or a[i-1][0] != x: b.append(y)
else: c.append(y)
b.sort(reverse=True)
c.sort(reverse=True)
b += [-1<<40]*n; c += [-1<<40]*n
ans = 0; s = sum(c[:k])
for i in range(1, k+1):
s += b[i-1] - c[k-i]
ans = max(ans, i*i + s)
return ans