ホワイト準アンテナ(18310)

n.アンテナ

1.ヒント

1)シンプルな実装により、すべての家屋から残りの家屋までの距離の合計を計算できます。これはO（N 2）O（N^2）O（N 2）をもたらす。

2)ある家にアンテナを設置し、その家では左の家の数が右の家の数より多い場合は、ここに設置せずに左に移動するのが絶対に有利である。

3)指定された数列を並べ替えて、左側の家屋の数が右側の家屋の数と同じ点を検索します。もちろん、N 2frac{n}2 Nの2番目の位置となり、NNNが偶数であれば2つの答えがあるので、Nfrac{n-1}2 N1が正しい。

2.近接

絵を描いてみてもいいですか。

一番左の家と一番右の家111の位置にある家を選択すると、2つの家の間の距離は0+80+80+8です.
555にある家を選んだら、4+44+44+4です.
777の位置にある家を選んだら、6+26+26+2です.
999の場所にある家を選択した場合は、8+08+08+0
どの家を選んでも、一番左の家と一番右の家の間の距離は固定されています.この言葉の意味はこれ以上低くしてはいけない.555と777の立場では、外側の111555と777の間の距離が222であれば、より大きくなる.
そのため、真ん中の家を選ぶのが最適です.これをソートします.

公式で表現できますか?

他の方法で問題を解決することもできます.C[x]C[x]C[x]はxxxの位置にある家の数を格納する.P[x]P[x]P[x]は、xxxの位置にある家屋座標値の和を記憶する.
家のアンテナを選ぶと、すべての家までの距離が
左:xΣk=0 x-1 C[k]  −∑k=0x−1P[k]x\displaystyle\sum_{k=0}^{x-1}C[k]\\-\displaystyle\sum_{k=0}^{x-1}P[k]xk=0∑x−1​C[k]  1 P[k]で求めることができます.
右側:Σk=x+110000 P[k]  −x∑k=x+1100000C[k]\displaystyle\sum_{k=x+1}^{100000}P[k] \\- x\displaystyle\sum_{k=x+1}^{100000}C[k]k=x+1∑100000​P[k]  -xk=x+1∑100000C[k].
CCCとPPPは累加配列により実現できる.

3.実施

累積配列を使用するプール.

public class Main {
	
	static long sum(long[] S, int i, int j) {
		if (i > j) return 0;
		return S[j] - (i == 0 ? 0 : S[i - 1]);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] S = new int[N];
		// P[x] = x위치 이하 좌표값의 합 C[x] = x위치 이하 좌표의 개수 합      
		long[] P = new long[100001]; long[] C = new long[100001];
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) S[i] = Integer.parseInt(st.nextToken());
		for (int x : S) { P[x] += x; C[x]++; }
		for (int i = 1; i <= 100000; i++) { 
			P[i] += P[i - 1]; C[i] += C[i - 1];
		}
		long min = Long.MAX_VALUE;
		int ret = 100000;
		for (int x : S) {
			long sum = sum(C, 0, x - 1) * x - sum(P, 0, x - 1) +
			sum(P, x + 1, 100000) - sum(C, x + 1, 100000) * x;
			if (min >= sum) {
				if (min > sum || (min == sum && ret > x)) ret = x;
				min = sum;
			}
		}
		System.out.println(ret);
	}

}

1）時間複雑度

ソートは中心値を探すプールの時間的複雑さを支配するので,O(Nlgn)O(Nlgn)O(Nlgn)O(Nlgn)O(Nlgn)である.このプールはソートする必要がないので、O(N)O(N)O(N)です.

2）テストケース