题目描述：
小扣在秋日市集入口处发现了一个数字游戏。主办方共有 N 个计数器，计数器编号为 0 ~ N-1。每个计数器上分别显示了一个数字，小扣按计数器编号升序将所显示的数字记于数组 nums。每个计数器上有两个按钮，分别可以实现将显示数字加一或减一。小扣每一次操作可以选择一个计数器，按下加一或减一按钮。
主办方请小扣回答出一个长度为 N 的数组，第 i 个元素( $0 \le i \lt N$ )表示将 0~i 号计数器 初始 所示数字操作成满足所有条件 nums[a]+1 == nums[a+1],(0 <= a < i) 的最小操作数。回答正确方可进入秋日市集。
由于答案可能很大，请将每个最小操作数对 1,000,000,007 取余。
数据范围：
$1\le nums.len \le 10^5, 1\le nums[i] \le 10^3$
题解：
首先如果满足以 $1$ 为单位递增，那么 $nums[i] - i$ 就是完全相同。转化为 $nums[i] - i$ ，操作最少次使得所有数字都是相等的。这个问题之前见过，就是要转化为中位数。该题需要对每个前缀求中位数，之前的题目是与顺序无关，可以直接排序，然后二分求代价。但是这个题目和数字的顺序有关，需要一遍维护中位数，一边维护小于中卫数的和，大于中位数的和。
可以使用对顶堆动态求中位数，而且可以动态维护两个堆的和。使用一个最大堆 $left$ ，一个最小堆 $right$ 。需要注意的是取模。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Median
{
private:
const static int mod = 1e9 + 7;
priority_queue<int> left;
priority_queue<int, vector<int>, greater<int>> right;
public:
int leftSum;
int rightSum;
Median() : leftSum(0), rightSum(0) {}
vector<int> getNum(vector<int> &nums)
{
int n = nums.size();
vector<int> ans(n);
for (int i = 0; i < n; ++i)
{
push(nums[i]);
ans[i] = getMedian();
}
return ans;
}
void push(int x)
{
if (left.size() == right.size())
{
if (left.empty() || x >= left.top())
{
right.push(x);
rightSum = (rightSum + x) % mod;
}
else
{
right.push(left.top());
leftSum = (leftSum + x - left.top()) % mod;
rightSum = (rightSum + left.top()) % mod;
left.pop();
left.push(x);
}
}
else
{
if (x <= right.top())
{
left.push(x);
leftSum = (leftSum + x) % mod;
}
else
{
left.push(right.top());
leftSum = (leftSum + right.top()) % mod;
rightSum = (rightSum + x - right.top()) % mod;
right.pop();
right.push(x);
}
}
}
int getMedian()
{
return right.top();
}
};
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static long long mod = 1e9 + 7;
const long long INF_LL = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
priority_queue<int> left;
priority_queue<int, vector<int>, greater<int>> right;
vector<int> numsGame(vector<int> &nums)
{
int n = nums.size();
for (int i = 0; i < n; ++i)
nums[i] -= i;
vector<int> ans(n);
Median median;
for (int i = 0; i < n; ++i)
{
median.push(nums[i]);
ans[i] = ((median.rightSum - (i % 2 == 0) * median.getMedian() - median.leftSum) % mod + mod) % mod;
}
return ans;
}
};
|