頭整理が大変だけど、考え方はわかる。
問題概要
は正の奇数である。
個の整数
が与えられる。以下の
個のクエリに答えよ。
- 各クエリでは整数
が与えられる
個の整数
を 2 個ずつペアにして
組のペアを作る
- それぞれのペアの「数値の差」の総和として、考えられる最小値を答えよ
制約
考えたこと
まずは 1 個のクエリに答えることを考える。これは比較的簡単にわかる。 個の整数を小さい順に並べて
としたとき、
をペアにする (差は
)
をペアにする (差は
)
- ...
をペアにする (差は
)
という風にするのが最適となる。以上で、1 つのクエリに対する問題は解けた。
クエリ処理へ
毎回のクエリにおいて 個の値のうちの
個は毎回共通であることに注目する。まずは、あらかじめ
を小さい順に並べておこう。
このとき、クエリごとに挿入される値 は、数列
のどこかに挿入されることになる (挿入される位置は lower_bound() によって求められる)。この挿入操作による影響は、実は挿入された箇所の近辺のみに限られる。
たとえば で、
が「左側に 2 個、右側に 5 個」の位置に挿入されるとしたとき
- 「左 2 個分」は数列
の左側から 2 個分に関する答え
- 「右 4 個分」は数列
の右側から 4 個分に関する答え
- さらに
をすべて合計したものが答えになることがわかる。
これを求めるためには、次のような「左右からの累積和」を持っておくと良さそう。
- left[
] :=
の左
個分に関する答え (
は偶数)
- right[
] :=
の右
個分に関する答え (
は偶数)
一般に、 が挿入されるときに、左側に
個あったとする。
が偶数のとき:left[
] + right[
] +
が奇数のとき:left[
] + right[
] +
全体を通した計算量は次のようになる。
- 数列
のソート:
- 累積和 left, right の前処理:
- 各クエリに答える:
コード
#include <bits/stdc++.h> using namespace std; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } const long long INF = 1LL<<60; int main() { int N, M; cin >> N >> M; vector<long long> X(N), W(M); for (int i = 0; i < N; ++i) cin >> X[i]; for (int i = 0; i < M; ++i) cin >> W[i]; sort(X.begin(), X.end()); vector<long long> left(N+1, 0), right(N+1, 0); for (int i = 2; i < N; i += 2) { left[i] = left[i-2] + X[i-1] - X[i-2]; right[i] = right[i-2] + X[N-i+1] - X[N-i]; } long long res = INF; for (auto w : W) { int i = lower_bound(X.begin(), X.end(), w) - X.begin(); if (i % 2 == 0) chmin(res, left[i] + right[N-i-1] + X[i] - w); else chmin(res, left[i-1] + right[N-i] + w - X[i-1]); } cout << res << endl; }