これ難易度8なんだ…。
https://leetcode.com/problems/minimum-operations-to-make-array-equal-to-target/description/
問題
整数列Aが与えられる。
1回の処理で、Aの部分列をインクリメント又はデクリメントできる。
数列AをBにするのにかかる最小処理回数を求めよ。
解法
BとAの各要素の差を取った数列をCとし、Cの階差数列をDとする。
1回の処理で、Dの1要素をインクリメント、1要素でデクリメントできる。
よって、解はDのうち正の値の総和とできる。
class Solution { public: long long minimumOperations(vector<int>& nums, vector<int>& target) { vector<int> V; int pre=0; int i; FOR(i,nums.size()) { int x=nums[i]-target[i]; V.push_back(x-pre); pre=x; } V.push_back(-pre); ll sum=0; FORR(v,V) if(v>0) sum+=v; return sum; } };
まとめ
かなり典型な気がするけど、LeetCodeでは出にくいタイプの問題なのかな。