3086. 拾起 K 个 1 需要的最少行动次数

3086. 拾起 K 个 1 需要的最少行动次数

---

题目链接：3086. 拾起 K 个 1 需要的最少行动次数

代码如下：

//参考链接:https://leetcode.cn/problems/minimum-moves-to-pick-k-ones/solutions/2692009/zhong-wei-shu-tan-xin-by-endlesscheng-h972
class Solution
{
public:
long long minimumMoves(vector<int>& nums, int k, int maxChanges)
{
vector<int> pos;
int c = 0;//nums中连续1的长度
for (int i = 0; i < nums.size(); i++)
{
if (nums[i] == 0) { continue; }
pos.push_back(i);//记录1的位置
c = max(c, 1);
if (i > 0 && nums[i - 1] == 1)
{
if (i > 1 && nums[i - 2] == 1)
{
c = 3;//有3个连续的1
}
else
{
c = max(c, 2);//有2个连续的1
}
}
}

c = min(c, k);
if (maxChanges >= k - c)
{
//其余k-c个1可以全部用两次操作得到
return max(c - 1, 0) + (k - c) * 2;
}

int n = pos.size();
vector<long long> sum(n + 1);
for (int i = 0; i < n; i++)
{
sum[i + 1] = sum[i] + pos[i];
}

long long res = LLONG_MAX;
//除了maxChanges个数可以用两次操作得到，其余的1只能一步步移动到pos[i
int size = k - maxChanges;
for (int right = size; right <= n; right++)
{
//s1+s2是j在[left,right)中所有pos[j]到index=pos[(left+right)/2] 的距离之和
int left = right - size;
int i = left + size / 2;
long long index = pos[i];
long long s1 = index * (i - left) - (sum[i] - sum[left]);
long long s2 = sum[right] - sum[i] - index * (right - i);
res = min(res, s1 + s2);
}
return res + maxChanges * 2;
}
};

原文地址：https://blog.csdn.net/weixin_45256307/article/details/140730047

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！