Mua 3 tặng 1 - LCOJ: Luyện Code Online Judge

DISCOUNT - Mua 3 tặng 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

Siêu thị Vincom Sơn La đang có đợt giảm giá. Siêu thị có ~n~ mặt hàng đánh số từ ~1~ đến ~n~, mặt hàng thứ ~i~ có giá là ~c_i~. Trong đợt giảm giá này, cứ mua ~3~ mặt hàng thì siêu thị sẽ giảm giá cho mặt hàng có giá cao nhất trong ~3~ mặt hàng đó.

Yêu cầu: Hãy tính số tiền tối thiểu cần bỏ ra để mua hết ~n~ mặt hàng của siêu thị.

Input

Dòng đầu tiên ghi số ~n~ là số mặt hàng của siêu thị;
Dòng thứ hai ghi ~n~ số nguyên dương ~c_1,c_2,…,c_n\ (1≤c_i≤10^9)~. Hai số liên tiếp được ghi cách nhau một khoảng trắng.

Giới hạn:

Subtask #1: 60% số điểm của bài có ~1≤n≤1000~;
Subtask #2: 40% số điểm còn lại của bài có ~1000< n≤10^5~.

Output

Một số nguyên duy nhất là số tiền tối thiểu cần bỏ ra để mua hết ~n~ mặt hàng của siêu thị.

Sample

Input #1

5
10 3 7 5 8

Output #1

Hint

Giải thích: Ta mua mặt hàng ~1,2,3~ sẽ được khuyến mại mặt hàng ~1~ nên cần trả ~10~ đồng, mua mặt hàng ~4,5~ cần trả ~13~ đồng nữa. Tổng cộng cần trả ~23~ đồng.

Problem source: Chuyên Sơn La Online Judge

Bình luận

Please read the guidelines before commenting.

spoil!

ý tưởng 
sắp xếp mảng tăng dần 
Mỗi lần lấy 2 món rẻ nhất (phải trả tiền) + 1 món đắt nhất (được miễn phí). Lặp lại đến hết

code tham khảo

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    int n;
    cin >> n;
    int a[n+1];
    for (int i = 1; i <= n; ++i) cin >> a[i];
    sort(a+1, a+1+n);
    long long ans = 0;
    int i = n, j = 1;
    while (i >= j) {
        if (i - 1 >= j) {
            ans += a[j] + a[j + 1];
            j += 2;
        } else {
            ans += a[j];
            j++;
        }
        i--;
    }
    cout << ans << endl;
}

-3

theguy777_jaboi đã bình luận lúc 17, Tháng 7, 2024, 2:45 ← chỉnh sửa →

Ý tưởng: tính tổng tất cả món đồ rồi trừ n/3 món đồ đầu tiên (nhớ sort ngược lại)

-3

theguy777_jaboi đã bình luận lúc 17, Tháng 7, 2024, 1:12

6

dinhvantung0611 đã bình luận lúc 23, Tháng 1, 2024, 9:53 ← chỉnh sửa →

Ý tưởng: ta có thể mua 3 món đồ không cần nằm cạnh nhau cũng được (trong đó có 2 món có giá tiền thấp nhất và 1 món có giá tiền lớn nhất).

CƯỜNG GIẢ HỌ ĐINH. VẠN CỔ TỐI CƯỜNG