小扣在秋日市集入口处发现了一个数字游戏。主办方共有 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 取余。

示例 1:

输入: nums = [3,4,5,1,6,7]

输出: [0,0,0,5,6,7]

解释:

  • i = 0,[3] 无需操作
  • i = 1,[3,4] 无需操作;
  • i = 2,[3,4,5] 无需操作;
  • i = 3,将 [3,4,5,1] 操作成 [3,4,5,6], 最少 5 次操作;
  • i = 4,将 [3,4,5,1,6] 操作成 [3,4,5,6,7], 最少 6 次操作;
  • i = 5,将 [3,4,5,1,6,7] 操作成 [3,4,5,6,7,8],最少 7 次操作; 返回 [0,0,0,5,6,7]。

示例 2:

输入: nums = [1,2,3,4,5]

输出: [0,0,0,0,0]

解释: 对于任意计数器编号 i 都无需操作。

示例 3:

输入: nums = [1,1,1,2,3,4]

输出: [0,1,2,3,3,3]

解释:

  • i = 0,无需操作;
  • i = 1,将 [1,1] 操作成 [1,2] 或 [0,1] 最少 1 次操作;
  • i = 2,将 [1,1,1] 操作成 [1,2,3] 或 [0,1,2],最少 2 次操作;
  • i = 3,将 [1,1,1,2] 操作成 [1,2,3,4] 或 [0,1,2,3],最少 3 次操作;
  • i = 4,将 [1,1,1,2,3] 操作成 [-1,0,1,2,3],最少 3 次操作;
  • i = 5,将 [1,1,1,2,3,4] 操作成 [-1,0,1,2,3,4],最少 3 次操作; 返回 [0,1,2,3,3,3]。

提示:

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^3

输入格式

nums = [整数数组]

输出格式

[整数数组]

题目分析

可以将每个元素转换为 nums[i] - i, 那么问题变成 仓库选址 问题。

代码实现

Sorting

class Solution {
public:
    int mid, n;
    int minMoves2(vector<int>& nums) {
        n = nums.size();
        sort(nums.begin(), nums.end());
        if(n & 1) mid = nums[n >> 1];
        else mid = ((nums[n >> 1] + nums[(n >> 1) - 1])) >> 1;
        int ans = 0;
        for(auto& t : nums) ans += abs(t - mid);
        return ans;
    }
    vector<int> numsGame(vector<int>& nums) {
        vector <int> a, ans;
        for(int i = 0; i < nums.size(); ++i) {
            nums[i] -= i;
            a.push_back(nums[i]);
            ans.push_back(minMoves2(a));
        }
        return ans;
    }
};

Heap

class Solution {
public:
    vector<int> numsGame(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n);
        priority_queue<int> lower;
        priority_queue<int, vector<int>, greater<>> upper;
        long long mod = 1e9 + 7;
        long long lowerSum = 0, upperSum = 0;
        for (int i = 0; i < n; i++) {
            int x = nums[i] - i;
            if (lower.empty() || lower.top() >= x) {
                lowerSum += x;
                lower.push(x);
                if (lower.size() > upper.size() + 1) {
                    upperSum += lower.top();
                    upper.push(lower.top());
                    lowerSum -= lower.top();
                    lower.pop();
                }
            } else {
                upperSum += x;
                upper.push(x);
                if (lower.size() < upper.size()) {
                    lowerSum += upper.top();
                    lower.push(upper.top());
                    upperSum -= upper.top();
                    upper.pop();
                }
            }
            if ((i + 1)
                res[i] = (upperSum - lowerSum)
            } else {
                res[i] = (upperSum - lowerSum + lower.top())
            }
        }
        return res;
    }
};
分类: GreedyHeapMathSort

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status