Skip to content

Latest commit

 

History

History
57 lines (34 loc) · 2.2 KB

2011-05-01-2-pku-2231-moo-volume.md

File metadata and controls

57 lines (34 loc) · 2.2 KB
layout title date tags
post
[POJ] 2231 - Moo Volume
2011-05-01
POJ
sort | 排序
combinatorics | 組合數學

題目網址:2231 - Moo Volume

題目概述

農夫約翰擁有 N 頭牛,每一頭牛都會跟另外 N - 1 頭牛交談,所有的牛都處於數線上的一點。

牛與牛之間交談的音量為他們之間的距離絕對值。因此,若 A 牛的座標為 XA,而 B 牛的座標為 XB。他們交談的音量則為 XA - XB 的絕對值 abs(XA-XB)。

現在要求求出所有牛交談的音量總和。

Technique Detail

  • 牛的數量 N, 1 ≤ N ≤ 10,000

輸入格式

每一筆測試資料由一個整數 N 開始,表示農夫約翰有 N 頭牛。接下來有 N 行,每行一個整數 Xi ,表示該頭牛所在數線上的座標。

輸出格式

對於每一筆測試資料,輸出只有一行,且只含有一個整數,即為所有牛交談的音量總和。


解題思路

最直覺的方法就是,O( N2 ) 枚舉每一個配對即可,但 N 的範圍可達 10,000,如此 O( N2 ) 的方法必定會造成 TLE,於是需要一個更快的方法。我們將每隻牛的位置畫出來,若以牛的位置做分割點,數線將會被切成一段一段的,共 N - 1 段。

1 - 2 - 3 - … - ( N - 1 ) - N

可以發現:

區段 使用次數
1-2 1 × ( N - 1 ) × 2
2-3 2 × ( N – 2 ) × 2
( N - 1 )-N ( N - 1 ) × 1 × 2

因為 1-2 這段的左邊有 1 頭牛,右邊有 N – 1 頭牛,每頭牛都會跟另外 N - 1 頭牛交談,因此是雙向的,所以會使用 1 × ( N – 1 ) × 2 次,其他的線段也依此類推…。

因此我們可以在線性的時間 O( N )內求出解。但是,題目並不會依照座標順序給你牛的位置,所以我們必須先做一次排序的動作。所以這題的時間複雜度為 O( N × log N )。

Time Complexity: O( N × log N )

Source Code

<script src="https://gist.github.com/KuoE0/1611911.js"></script>

Source code on gist.