CSAcademy Lonely Points - kou6839の日記

csacademy.com

<問題概要>

要素数 ${Ｎ}$ の数列 ${A_0,A_1,...A_{N-1} }$ が与えられる。

数列Aは昇順にならんでおり、 ${N}$ 点のx座標を表している。

一度だけ、数列Aの数字１つを選び、好きな座標(数字）に書き換えることができる。

このような操作をし、隣り合った(N-1つ)の座標の差の最大値を最小にしたとき、その値はいくつか。

<解説>

一番差が大きいところに、どこからか数字を持ってきて2つの数字の真ん中に置き、差を半分にします。それと、２番目に大きいものを比較し、大きいほうが答えになります。 (コードではpriority_queueで管理しています)

一番差が大きいもの以外の間においても答えは変わらないので、その必要はありません。

次に、どこから数字を持ってくるのかということを考えますが、両端のどちらか隣との差が大きいほうになります。

端の数字を持ってくる場合は、その隣との座標の差そのものがなくなるため、差の最大値が増えることがありません。

一方、端ではない数字 ${A_i}$ を移動させる際には ${A_{i+1}-A_{i-1}}$ が増加してしまい、移動する際のペナルティが発生します。

後者でも答えに影響がないこともありますが、ペナルティがない方を選んだほうが実装も楽です。

<コード>

int main(){

int n;
cin >> n;
vi a(n);
rep(i, n)cin >> a[i];

//[tex:{A_0}を移動させる場合]
priority_queue<int> pq;
for (int i = 1; i + 1 < n; i++) {
pq.push(a[i + 1] - a[i]);
}
int maxp = pq.top(); pq.pop();
pq.push((maxp + 1) / 2);
int ans = pq.top();

//[tex:{A_{N-1}}を移動させる場合]
pq = priority_queue<int>();
for (int i = 0; i + 1 < n-1; i++) {
pq.push(a[i + 1] - a[i]);
}
maxp = pq.top(); pq.pop();
pq.push((maxp + 1) / 2);
ans = min(ans, pq.top());
P(ans);
return 0;
}