Edited at

ABC094 C - Many Medians (300点)


問題概要

問題のリンク

$N$ 個の数 $X_1,X_2,...,X_N$ が与えられる。($N$ は偶数。)

ここで、$i=1,2,...,N$ に対して,$X_1,X_2,...,X_N$ から $X_i$ のみを除いたもの、すなわち $X_1,X_2,...,X_{i−1},X_{i+1},...,X_N$ の中央値を $B_i$ とする。$i=1,2,...,N$ に対して,$B_i$ を求めよ。


制約条件


  • $2≤N≤200000$

  • $N$ は偶数

  • $1≤X_i≤10^9$

  • 入力はすべて整数


考えたこと

まず配列$X$から$X_i$を除いた配列を作って中央値を求めるという方法が思いつくが、この時C#だと Remove メソッドの計算量は$O(N)$となるので、全ての$X$に対して上の処理をすると$O(N^2)$となるのでTLEする。

よって$O(N)$以下に計算量を収めたい。

偶数個の要素($N$)をもつ配列$X$から$X_i$、つまり1つの要素を除いた配列の中央値を求めるので、中央値は$X_{n/2-1}$か$X_{n/2}$のどちらかとなる。

以下の入力例1での場合を見てみるとわかりやすい。

IMG_1345.JPG

よって、$X_i$が$X_{n/2-1}$より左側、すなわち$X_{n/2-1}$以下の場合は$X_{n/2}$が答えとなり、$X_{n/2}$より右側、すなわち$X_{n/2}$以上の場合は$X_{n/2-1}$が答えとなる。

この時計算量は$O(N)$となる。


解答


c.cs

using System;

using System.Collections.Generic;
using System.Linq;

class Program
{
static void Main(string[] args) {
int n = int.Parse(Console.ReadLine());
List<int> x = Console.ReadLine().Split().Select(int.Parse).ToList();
List<int> l = new List<int>(x);
l.Sort();
for(int i = 0; i < n; i ++) {
Console.WriteLine(solve(n,l,x[i]));
}
}
static int solve(int n, List<int> l, int x) {
int ans = 0;
if(x <= l[n/2-1]) ans = l[n/2];
if(x >= l[n/2]) ans = l[n/2-1];
return ans;
}
}