4507 . 星冰樂買一送一

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

餘切
$\Huge\text{freeh1}$

User's AC Ratio

93.3% (14/15)

Submission's AC Ratio

52.2% (24/46)

Tags

Low Greedy 小社賽

Description

知名咖啡店Starburst正在進行一個星冰樂買一送一的活動。最懂的找到店家優惠的Brine當然要去狠狠地喝一波了。

已知Starburst這次買一送一的規則如下：

Starburst的員工Kirito會將n杯星冰樂放成一排，而從左數過來第$i$杯的星冰樂價錢為$S_i$。另外，如果你選擇買其中的某一杯星冰樂，那你可以免費拿走隨意一杯與其相鄰的星冰樂。在你拿完你買的和送的星冰樂之後，架上的星冰樂會自動靠攏把空隙填滿。

想請問Brine最少花多少錢就可以喝到每一杯星冰樂？

Input Format

$n$

$S_1\;S_2\;S_3...S_n$

$1\le n \le 10^6$，且保證$n$為偶數

$1\le S_i \le 10^9$

Output Format

請輸出一個整數，代表Brine要花的錢

Sample Input 1

4
1 4 2 3

Sample Output 1

3

Hints

Problem Source

111年小社賽pB

Subtasks

No. Testdata Range Score
1 0~20 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Memory Limit (RSS, KiB) Output Limit (KiB) Subtasks
0 1000 250000 250000 65536 1
1 1000 250000 250000 65536 1
2 1000 250000 250000 65536 1
3 1000 250000 250000 65536 1
4 1000 250000 250000 65536 1
5 1000 250000 250000 65536 1
6 1000 250000 250000 65536 1
7 1000 250000 250000 65536 1
8 1000 250000 250000 65536 1
9 1000 250000 250000 65536 1
10 1000 250000 250000 65536 1
11 1000 250000 250000 65536 1
12 1000 250000 250000 65536 1
13 1000 250000 250000 65536 1
14 1000 250000 250000 65536 1
15 1000 250000 250000 65536 1
16 1000 250000 250000 65536 1
17 1000 250000 250000 65536 1
18 1000 250000 250000 65536 1
19 1000 250000 250000 65536 1
20 1000 250000 250000 65536 1
Submit
Back to Top