【反悔堆反悔贪心】2813. 子序列最大优雅度

本文涉及知识点

反悔堆反悔贪心

LeetCode 2813. 子序列最大优雅度

给你一个长度为 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 <= 10⁵
items[i].length == 2
items[i][0] == profiti
items[i][1] == categoryi
1 <= profiti <= 10⁹
1 <= categoryi <= n
1 <= k <= n

反悔贪心

最大数：某个类型最大利润。
枚举类型t，分别计算最大和：
小根堆maxHeap记录各类型的最大值，大根对otherHeap记录各类型非最大值。
如果maxHeap的元素数量大于k，则出栈到k。更新结果。操作一
t = maxHeap.size()。将otherHeap中的数，移到headMax直到maxHeap 的元素数量位k。更新结果。操作二
如果otherHeap非空，且栈顶元素大于maxHeap栈顶元素，则移动元素到maxHeap。t–，更新结果。操作三
性质一：因为是otherHeap是从大到小出栈，故不会替换来源于otherHeap的数，只会替换来源于maxHeap的数，即类型数减1。
性质二：otherHeap中的x1替换maxHeap中的数x2时，和x类型相同的最大树一定还在maxHeap中。x2在maxHeap中，说明比x2的类型最大数都在堆中。x2是最后出堆，故比x2大的数仍然没有出堆。故操作三不会增加类型。
性质三：结合性质一、性质二操作三必定让会类型减少1。
性质四：操作一出栈的数永远不会用到。操作一和操作二不会同时存在。操作三只会让maxHeap的数越大越大。即操作一出栈的数永远小于等于maxHeap中的元素。类型越来越少的情况下，和不变或变小，一定被淘汰。

数学归纳法：本方法必定找到最优解

初始状态是最大类型的最优接：
操作一后：堆中就是最大的k个最大数，显然是最后解。
操作二后：所有类型最大值都在里面。由于类型已经到达最大值，所有无法增加。只需要保证和最大。
t个类型的最优解通过操作三操作一次后必定是t-1的最优解
想让t减少1，唯一的方案：
最大值删除一个数，非最大值增加一个数。显然要删除最小值，且增加最大值，且增加的数大于删除的数。
按操作三的方法t一定会变成0。最后一个最大值一定是所有数的最大值，不会被淘汰。

好理解的方案

vMax升序记录最大值，vOther升序记录其它数。
枚举i个元素来自于vMax，其它元素来自于vOther：i $\in$ [1,min(k,vMax.size())] 同 (k-i) >= 0 ，且(k-i) <= vOther.size()
类型为i的最大价值就是：vMax的前i个元素和+ vOther的前k-i个元素 + i²。
注意：有可能类型不为i，即vOther的前(k-i)个元素对应的最大值没有被选择，此方案的优雅度计算少了。
但此方案就算不计算少了，也会被方案二淘汰：将这些元素换成对应的最大值。
求最大值时，某个被淘汰的方案被算小了，不会影响最终结果。

代码

核心代码

class Solution {
public:
	long long findMaximumElegance(vector<vector<int>>& items, int k) {
		sort(items.begin(), items.end(), std::greater<>());
		unordered_set<int> setHas;
		priority_queue<int,vector<int>,greater<>> maxHeap;
		priority_queue<int> otherHeap;
		long long sum = 0;
		for (const auto& v : items) {
			if (setHas.count(v[1])) {
				otherHeap.emplace(v[0]);
			}
			else {
				maxHeap.emplace(v[0]);
				sum += v[0];
				setHas.emplace(v[1]);
			}
		}
		while (maxHeap.size() > k) {
			sum -= maxHeap.top();
			maxHeap.pop();
		}
		long long t = maxHeap.size();
		while (maxHeap.size() < k) {
			sum += otherHeap.top();
			maxHeap.emplace(otherHeap.top());
			otherHeap.pop();
		}
		long long ret = sum + t * t;
		for (t--; t > 0; t--) {
			if (otherHeap.size() && (otherHeap.top() > maxHeap.top())) {
				sum += otherHeap.top();
				sum -= maxHeap.top();
				maxHeap.pop();
				maxHeap.emplace(otherHeap.top());
				otherHeap.pop();
				ret = max(ret, sum + t * t);
			}
		}
		return ret;
	}
};

单元测试

template<class T1, class T2>
void AssertEx(const T1& t1, const T2& t2)
{
	Assert::AreEqual(t1, t2);
}

template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{
	Assert::AreEqual(v1.size(), v2.size());
	for (int i = 0; i < v1.size(); i++)
	{
		Assert::AreEqual(v1[i], v2[i]);
	}
}

template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{
	sort(vv1.begin(), vv1.end());
	sort(vv2.begin(), vv2.end());
	Assert::AreEqual(vv1.size(), vv2.size());
	for (int i = 0; i < vv1.size(); i++)
	{
		AssertEx(vv1[i], vv2[i]);
	}
}

namespace UnitTest
{	
	vector<vector<int>>items;
	int k;
	TEST_CLASS(UnitTest)
	{
	public:
		TEST_METHOD(TestMethod00)
		{
			items = { {3,2},{5,1},{10,1} }, k = 2;
			auto res = Solution().findMaximumElegance(items, k);
			AssertEx(17LL, res);
		}
		TEST_METHOD(TestMethod01)
		{
			items = { {3,1},{3,1},{2,2},{5,3} }, k = 3;
			auto res = Solution().findMaximumElegance(items, k);
			AssertEx(19LL, res);
		}
		TEST_METHOD(TestMethod02)
		{
			items = { {1,1},{2,1},{3,1} }, k = 3;
			auto res = Solution().findMaximumElegance(items, k);
			AssertEx(7LL, res);
		}
		TEST_METHOD(TestMethod03)
		{
			items = { {2,2},{8,3},{8,3} }, k =2;
			auto res = Solution().findMaximumElegance(items, k);
			AssertEx(17LL, res);
		}
	};
}