結論から言えば「非負数と負数にわけて総和を計算する」です。
問題の趣旨
長さ N の数列 A がある。
A[i]に 1 を加算または減算するという操作を 0 回以上繰り返すことで A の要素をすべて x にしたい。
必要な操作の最小回数を求めよ。
これは「A 全体から x を引いたあとその絶対値の総和を求めよ」という問題と同じです。
非負数と負数にわけて絶対値の総和を計算する
ソートすればある部分を境界として非負数と負数にわけることができます。境界を探すには二分探索法を使うのがよさそうです。あとは非負数部分の総和と負数部分の総和を計算してそれぞれの絶対値を足せばそれが解となります。区間[a, b]の総和を何度も計算するときは累積和を使うと便利です。
A 全体からある値 x を引いたあとの絶対値の総和を計算するときは A を x 未満と x 以上にわけてから、非負数部分の総和から x の個数倍を引いたものと負数部分の総和から x の個数倍を引いたものの総和を計算します。そのあとそれぞれの絶対値を足せば解を得ることができます。
|
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 |
class Program { static void Main() { SourceExpander.Expander.Expand(); int N, Q; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; Q = vs[1]; } long[] A = Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray(); A = A.OrderBy(_ => _).ToArray(); // 累積和をつかって A[left] から A[right] までの総和を素早く計算できるようにする long[] B = new long[N + 1]; for (int i = 0; i < N; i++) B[i + 1] = B[i] + A[i]; long GetSum(int left, int right) => B[right + 1] - B[left]; // 二分探索法で A から target を引いたあとの負数と非負数の境界線を取得する // A[i] >= target となる最小の i を取得すればよい int LowerBound(int target) { int ng = -1; int ok = A.Length; while (ok - ng > 1) { int mid = (ng + ok) >> 1; if (target - A[mid] <= 0) ok = mid; else ng = mid; } return ok; } for (int i = 0; i < Q; i++) { int x = int.Parse(Console.ReadLine()); int idx = LowerBound(x); long ans = 0; // [0, idx - 1] の総和：xを引くことで負数になる部分の総和 // idx：負数部分の個数 // （注意！）区間長が0になるときはなにもしない // （注意！）x * idx は int型の範囲を超える場合があるので long型へのキャストが必要 if (idx - 1 >= 0) ans += Math.Abs(GetSum(0, idx - 1) - x * idx); // [idx, N - 1] の総和：xを引くことで非負数になる部分の総和 // N - idx：非負数部分の個数 if (idx <= N - 1) ans += GetSum(idx, N - 1) - x * (N - idx); Console.WriteLine(ans); } } } |
