Hovanthong
Admin
Tổng số bài gửi : 101
Join date : 25/07/2010
Age : 30
Đến từ : Hưng nguyên-Nghệ An
 |  Tiêu đề: Xếp gạch  Tue 27 Jul 2010, 13:20 | |
| Cho một dãy N viên gạch lần lượt có độ cách nhiệt là các số a1.. aN. Nếu xếp lần lượt các viên gạch theo trình tự đó thì độ cách nhiệt cả khối là a1 + a2 + ... + aN + max(0, a2 - a1) + max(0, a3 - a2) + ... + max(0, aN - aN - 1). Nhiệm vụ của bạn là tìm cách xếp sao cho độ cách nhiệt của cả khối là lớn nhất có thể.
Dữ liệu
* Dòng đầu ghi số nguyên dương N (0 < n ≤ 10^5).
* N dòng sau mỗi dòng ghi một số ai ( 1 ≤ i ≤ N và 1 ≤ ai ≤ 10000).
Kết qủa
Ghi trên một dòng kết quả cần tìm.
Ví dụ
Dữ liệu:
4
5
4
1
7
Kết qủa
24
| |
|
littlelee
Admin
Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 29
Đến từ : Nghĩa địa
| |
Hovanthong
Admin
Tổng số bài gửi : 101
Join date : 25/07/2010
Age : 30
Đến từ : Hưng nguyên-Nghệ An
| | Tiêu đề: Re: Xếp gạch Wed 28 Jul 2010, 15:50 | |
| - Code:
-
Const MaxN=100001;
Var N,i:longint;
S:longint;
A:Array[1..MaxN] of longint;
procedure Sort(L,R:longint);
Var i,j,Key,Tam:longint;
Begin
If L>=R then Exit;
i:=L;
j:=R;
Key:=A[(L+R) div 2];
Repeat
While A[i]<Key do Inc(i);
While A[j]>Key do Dec(j);
If i<=j then
Begin
Tam:=A[i];
A[i]:=A[j];
A[j]:=Tam;
Inc(i);
Dec(j);
End;
Until i>j;
Sort(i,R);
Sort(L,j);
End;
BEGIN
Readln(N);
For i:=1 to N do
Begin
Readln(A[i]);
S:=S+A[i];
End;
Sort(1,N);
For i:=1 to N div 2 do
Begin
S:=S+A[N-i+1]-A[i];
End;
Writeln(S);
END.
| |
|
