Công ty đồ chơi X nhập khẩu n con búp bê gỗ. Các con búp bê được đánh số từ 1 tới n trong đó con búp bê thứ i là một hộp rỗng có kích thước là một số nguyên ai. Người ta có thể lồng con búp bê thứ i vào trong con búp bê thứ j nếu con búp bê thứ j đang rỗng và , với k là một số nguyên dương cho trước. Bằng cách lồng các con búp bê vào nhau theo cách như vậy, công ty X chỉ cần tìm chỗ đặt những con búp bê ngoài cùng (những con búp bê không nằm trong bất kỳ con búp bê nào khác) vào kho. Yêu cầu: Hãy giúp công ty X lồng các con búp bê vào nhau sao cho tổng kích thước các con búp bê ngoài cùng là nhỏ nhất.
Lời giải 1 :
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse = True)
b = []
sum = 0
for i in range(0,len(a)):
if len(b) == 0:
b.append(a[i])
sum += a[i]
else:
pos = 0
for j in range(0,len(b)):
if (b[j] > b[pos]):
pos = j
if b[pos] >= a[i]+k:
b[pos] = a[i]
else:
b.append(a[i])
sum+=a[i]
print(sum)
Lời giải 2 :
#include <bits/stdc++.h>
using namespace std;
long long a[100005],i,j,k,sum,n;
int main()
{
cin>>n>>k;
for (i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+1+n,greater<int>());
j=1,sum=a[1];
for (i=2;i<=n;i++){
if (a[i]+k<=a[j])
j++;
else
sum+=a[i];
}
cout<<sum;
}
Bạn có biết?
Tin học là một ngành khoa học chuyên nghiên cứu quá trình tự động hóa việc tổ chức, lưu trữ, xử lý và truyền dẫn thông tin của một hệ thống máy tính cụ thể hoặc trừu tượng. Tin học bao hàm tất cả các nghiên cứu và kỹ thuật có liên quan đến việc mô phỏng, biến đổi và tái tạo thông tin. Hãy tận dụng sức mạnh của tin học để giải quyết các vấn đề và sáng tạo ra những giải pháp mới!
Nguồn :
Wikipedia - Bách khoa toàn thưTâm sự lớp 8
Lớp 8 - Năm thứ ba ở cấp trung học cơ sở, học tập bắt đầu nặng dần và sang năm lại là năm cuối cấp, áp lực lớn dần. Hãy chú ý đến sức khỏe, cân bằng giữa học và nghỉ ngơi để đạt hiệu quả tốt nhất!
Nguồn :
sưu tậpCó thể bạn quan tâm
Copyright © 2024 Giai BT SGK