公式
A - 数値列の一致 / Matching Sequences 解説
by
A - 数値列の一致 / Matching Sequences 解説
by
physics0523
初心者の方へ
- AtCoder をはじめたばかりで何をしたらよいか分からない方は、まずは practice contest の問題A「Welcome to AtCoder」を解いてみてください。基本的な入出力の方法が載っています。
- また、プログラミングコンテストの問題に慣れていない方は、AtCoder Beginners Selection の問題をいくつか解いてみることをおすすめします。
- C++入門 AtCoder Programming Guide for beginners (APG4b) は、競技プログラミングのための C++ 入門用コンテンツです。
- Python入門 AtCoder Programming Guide for beginners (APG4bPython) は、競技プログラミングのための Python 入門用コンテンツです。
\(A,B\) の要素を並べ替えたりすることはできないので、 \(A_i\) と \(B_i\) とを合わせることを順に繰り返すしかありません。
一度の操作で \(A_i\) または \(B_i\) に \(1\) 加減することしかできないため、この \(2\) つを合わせるのに必要な操作回数は \(A_i\) と \(B_i\) との差の絶対値、すなわち \(|A_i-B_i| = \max(A_i,B_i) - \min(A_i,B_i)\) です。
\(A_i,B_i\) のうち大きい方について、この回数だけ \(1\) 減算すれば \(A_i=B_i\) とできます。
例えば、 \(A_i=5,B_i=9\) であるとき \(|A_i-B_i| = 4\) で、 \(B_i\) から \(4\) 回 \(1\) を減算することで \(A_i=B_i\) とできます。
これを全ての \(i\) にわたって足し合わせればよいです。
一連の流れは、 for 文によって実装できます。
実装例 (C++):
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(){
ll N;
cin >> N;
vector<ll> A(N),B(N);
for(auto &nx : A){cin >> nx;}
for(auto &nx : B){cin >> nx;}
ll res=0;
for(ll i=0;i<N;i++){ res+=abs(A[i]-B[i]); }
cout << res << "\n";
return 0;
}
