Không hỗ trợ Mobile

Chế độ luyện tập yêu cầu môi trường màn hình lớn để làm bài và chống gian lận hiệu quả. Vui lòng truy cập bằng máy tính (Desktop/Laptop) để tiếp tục thao tác.

Quay lại trang chủ

#1069 · Thay thế tổng chi phí - REPLACESUM

MÔ TẢ BÀI TOÁN

Avatar
Đề tạo bởi
GV. Bùi Phú Khuyên

Hôm nay Nhật được thầy Hùng cho một bài tập như sau: Cho một dãy số gồm N phần tử a_1,..., a_N và một số nguyên dương K.

Trong một thao tác, bạn được thực hiện:

  • Nếu trong mảng còn ít nhất K phần tử, bạn phải chọn ra K phần tử nhỏ nhất (hoặc chọn tất cả nếu số lượng phần tử trong mảng ít hơn K) rồi thay thế bằng tổng của chúng.
  • Chi phí cho mỗi lần thực hiện chính là hiệu của số lớn nhất và số nhỏ nhất trong các số vừa chọn.
  • Lặp lại thao tác đến khi nào trong mảng còn đúng một phần tử.

In ra phần tử cuối cùng xuất hiện trong mảng và tổng chi phí thực hiện.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên dương N là số lượng phần tử (1 \leq N \leq 2 \times 10^5) và số nguyên dương K (2 \leq K \leq N).
  • Dòng tiếp theo chứa N số nguyên a_i (0 \leq a_i \leq 10^9).

Dữ liệu ra

  • Dòng đầu tiên là phần tử cuối cùng xuất hiện trong mảng.
  • Dòng tiếp theo là tổng chi phí thực hiện.

Ràng buộc

  • 50% test có N \leq 2000.
  • 50% test còn lại không ràng buộc gì thêm.

BẢNG TỔNG QUAN KẾT QUẢ

# Tài khoản Kết suất Lúc nộp
1
T
Dương Ngọc Trâm @2080601170
83 ms 3888 KB
892 Bytes
08/03/2023
16:18
2
Lê Duy Hải @2280600799
98 ms 3928 KB
1410 Bytes
16/02/2024
19:23
3
T
Nguyễn Thăng Tiến @2180608641
100 ms 3896 KB
733 Bytes
14/05/2023
23:08
4
T
Nguyễn Thăng Tiến @2180608641
101 ms 3896 KB
716 Bytes
14/05/2023
23:04
5
Lê Duy Hải @2280600799
101 ms 3924 KB
933 Bytes
16/02/2024
19:27
6
Đ
Dương Thành Đạt @2280618273
103 ms 1780 KB
3019 Bytes
30/06/2024
13:54
7
T
Nguyễn Thăng Tiến @2180608641
105 ms 3892 KB
733 Bytes
14/05/2023
23:08
8
T
Nguyễn Tri Bão Thắng @2180601452
105 ms 3896 KB
1882 Bytes
02/12/2022
13:57
9
T
Nguyễn Thăng Tiến @2180608641
105 ms 3900 KB
736 Bytes
14/05/2023
23:06
10
L
Mai Dương Long @2380601236
109 ms 4112 KB
1343 Bytes
17/06/2024
12:08
11
B
Nguyễn Hữu Ngự Bình @2280600266
115 ms 3928 KB
762 Bytes
14/03/2024
22:24
12
Nguyễn Tri Bão Thắng @25807700104
116 ms 3932 KB
1781 Bytes
23/12/2025
13:32
13
Sơn Trung Chiến @25800600077
119 ms 1776 KB
1376 Bytes
28/12/2025
00:30
14
P
Lương Hoài Phong @2287700062
123 ms 3920 KB
873 Bytes
17/12/2025
16:57
15
T
Nguyễn Trung Tuyến @2011064511
125 ms 3920 KB
1081 Bytes
17/10/2025
11:57
16
T
Nguyễn Thăng Tiến @2180608641
132 ms 3872 KB
722 Bytes
14/05/2023
23:03
17
T
Nguyễn Thăng Tiến @2180608641
133 ms 3880 KB
722 Bytes
14/05/2023
23:03
18
T
Nguyễn Thăng Tiến @2180608641
135 ms 3876 KB
743 Bytes
14/05/2023
23:09
19
GV. Bùi Phú Khuyên @KBP0100298
140 ms 3880 KB
790 Bytes
01/12/2022
10:34
20
H
Trương Phước Hưng @2280601329
158 ms 3900 KB
825 Bytes
18/04/2024
11:19

LỊCH SỬ CÁ NHÂN

Vui lòng đăng nhập để xem lịch sử làm bài của bạn.

THẢO LUẬN BÀI TOÁN

Chưa có thảo luận nào cho bài này.

GỢI Ý & HƯỚNG DẪN

Với K = 2:

  • 2 số nhỏ nhất là 1 và 2, số được thay thế là 3 và chi phí thay thế là 2 - 1 = 1. Mảng hiện tại: [3, 3, 4].
  • 2 số nhỏ nhất là 3 và 3, số được thay thế là 6 và chi phí thay thế là 3 - 3 = 0. Mảng hiện tại: [6, 4].
  • 2 số nhỏ nhất là 6 và 4, số được thay thế là 10 và chi phí thay thế là 6 - 4 = 2. Mảng hiện tại: [10].

Vậy phần tử cuối cùng là 10 và chi phí là 1 + 0 + 2 = 3.

Viết code