本文主要是介绍差分转换+堆维护中位数，LeetCode LCP 24. 数字游戏，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、题目
1、题目描述
小扣在秋日市集入口处发现了一个数字游戏。主办方共有
N个计数器，计数器编号为0 ~ N-1。每个计数器上分别显示了一个数字，小扣按计数器编号升序将所显示的数字记于数组nums。每个计数器上有两个按钮，分别可以实现将显示数字加一或减一。小扣每一次操作可以选择一个计数器，按下加一或减一按钮。主办方请小扣回答出一个长度为
N的数组，第i个元素(0 <= i < N)表示将0~i号计数器 初始 所示数字操作成满足所有条件nums[a]+1 == nums[a+1],(0 <= a < i)的最小操作数。回答正确方可进入秋日市集。由于答案可能很大，请将每个最小操作数对
1,000,000,007取余。
2、接口描述
class Solution {
public:vector<int> numsGame(vector<int>& nums) {}
};3、原题链接
LCP 24. 数字游戏
二、解题报告
1、思路分析
正难则反
我们可以知道最后的状态是公差为1的递增序列，那么我们就是找到长度为i的等差数列的和与Σa[i]的差的最小值，那么我们知道等差数列每一项都等于a[0] + (i - 1)d，所以我们将前i个元素转化为公差为1的数列就等效为将a[i] - i这i个元素变相等。
而对于n个元素变相等的最小代价是转换为中位数，这是个常用的结论，可以自己试着证明一下。
我们令原数组每个元素减去i，然后维护一个最大堆一个最小堆
大根堆存右半值，小根堆存左半值，小根堆元素数目比大根堆多1或者相等。
当元素数目为奇数，那么大根堆的元素和减去小根堆元素和+小根堆堆顶即为答案
当元素数目为偶数，那么大根堆的元素和减去小根堆元素和即为答案
2、复杂度
时间复杂度：O(nlogn) 空间复杂度：O(n)
3、代码详解
class Solution {
public:
static constexpr int MOD = 1e9 + 7;vector<int> numsGame(vector<int>& nums) {priority_queue<int> pq1;priority_queue<int,vector<int>,greater<int>> pq2;int n = nums.size();if(n == 1) return {0};for(int i = 0; i < n; i++) nums[i] -= i;pq2.emplace(max(nums[0], nums[1])) , pq1.emplace(min(nums[0], nums[1]));long long s1 = pq1.top(), s2 = pq2.top();vector<int> ret{0, static_cast<int>(s2 - s1)};for(int i = 2; i < n; i++){if(nums[i] <= pq1.top())pq1.emplace(nums[i]), s1 += nums[i];else pq2.emplace(nums[i]), s2 += nums[i];if(pq1.size() == pq2.size() + 2) pq2.emplace(pq1.top()), s1 -= pq1.top(), s2 += pq1.top(), pq1.pop();else if(pq2.size() > pq1.size())pq1.emplace(pq2.top()), s2 -= pq2.top(), s1 += pq2.top(), pq2.pop();ret.emplace_back((i & 1 ? s2 - s1 : s2 - s1 + pq1.top()) % MOD);}return ret;}
};这篇关于差分转换+堆维护中位数，LeetCode LCP 24. 数字游戏的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
