Chia kẹo 1 - LCOJ: Luyện Code Online Judge

CANDY - Chia kẹo 1

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Tác giả:

Hiếu Nguyễn

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift

An và Bình là hai anh em. Ba của An sau chuyến đi công tác xa nhà trở về, mua cho An và Bình ~N~ gói kẹo, gói thứ ~i~ có ~A_i~ viên kẹo.

Để tránh việc tranh giành kẹo lẫn nhau, ba của An đã thống nhất việc chia kẹo theo cách sau:

Trước hết, ba của An chọn ra một số nguyên ~k~ (với ~1 ≤ k ≤ N~).
An sẽ được chia các gói kẹo từ ~1~ đến ~k~. Phần còn lại (các gói kẹo từ ~k + 1~ đến ~N~) sẽ được chia cho Bình.

Để tránh sự phân bua giữa hai anh em, ba của An muốn lựa chọn chỉ số ~k~ sao cho chênh lệch giữa tổng số lượng viên kẹo của hai anh em là nhỏ nhất có thể. Hãy giúp ông thực hiện điều này.

Input

Dòng đầu tiên gồm số nguyên ~N~ ~(2 ≤ N ≤ 200000)~ - số gói kẹo;
Dòng thứ hai gồm ~N~ số nguyên ~A_1, A_2, ..., A_N~ ~(1 ≤ A_i ≤ 10^9)~ - số viên kẹo trong từng gói kẹo.

Giới hạn:

Subtask#1 ~(50\%\text{ số điểm}): N ≤ 2000~;
Subtask#2 ~(50\%\text{ số điểm}):~ Không có ràng buộc gì thêm.

Output

In ra chênh lệch lượng kẹo nhỏ nhất có thể.

Sample

Input #1

5
5 1 3 2 6

Output #1

Input #2

6
4 5 3 6 1 2

Output #2

Input #3

2
100 100

Output #3

Hint

Trong ví dụ thứ nhất, nếu chọn ~k = 3~ thì tổng số kẹo An được chia là ~5 + 1 + 3 = 9~, tổng số kẹo Bình được chia là ~2 + 6 = 8~, chênh lệch lượng kẹo là ~|9 − 8| = 1~.
Trong ví dụ thứ hai, có hai cách chọn k tối ưu:
- Chọn ~k = 2~. Tổng số kẹo An được chia là ~4 + 5 = 9~, tổng số kẹo Bình được chia là ~3 + 6 + 1 + 2 = 12~, chênh lệch lượng kẹo là ~|9 − 12| = 3~.
- Chọn ~k = 3~. Tổng số kẹo An được chia là ~4 + 5 + 3 = 12~, tổng số kẹo Bình được chia là ~6 + 1 + 2 = 9~, chênh lệch lượng kẹo là ~|12 − 9| = 3~.

Problem source: Kc97ble - Free Contest

Bình luận

Please read the guidelines before commenting.

-1

include <bits/stdc++.h>

using namespace std ; int main () { int n ; cin >> n ;

vector &lt;long long> a(n) ;
vector &lt;long long> prefix (n + 1 , 0) ;

for (int i = 0 ; i < n ; i++){
    cin >> a[i] ;
}

for (int i = 1 ; i <= n ; i++ ){
    prefix[i] = prefix[i - 1] + a[i - 1] ;
}

long long min1 = LLONG_MAX ;

for (int i = 1 ; i < n ; i++ ){
    long long t1 = prefix[i] ;
    long long t2 = prefix[n] - prefix[i] ;
    long long sum = abs(t1 - t2) ;

    if (sum < min1) {
        min1 = sum ;
    }

cout << min1 ;

} code cho ai cần

4

nothingnew2013 đã bình luận lúc 23, Tháng 9, 2025, 8:19

rơi rơi,rơi cho vỡ thêm 1 lần vỡ vỡ vỡ cho nát tan 1 lần tan tan mong sao sẽ quen dần dần quay về qauy về nâng niu vết thương này thức dậy thức dậy thay ta lúc sang ngày lại là 1 người mới ra đời rồi một ngày sẽ thấy nó đẹp rồi 1 ngày sẽ thấy nó đẹp r 1 ngày sẽ thấy nó đẹp tuyệt vời