Bài tập  /  Bài đang cần trả lời

Trong nhà Nam hiện đang có n ổ cắm điện rời. Số lượng chỗ cắm trên mỗi ổ cắm điện này lần lượt là a1, a2, a3, ..., an chỗ cắm. Trên tường nhà Nam có một chỗ cắm cố định đang có điện. Vậy để cho một ổ cắm điện rời có điện thì phải cắm ổ cắm đó vào chỗ cắm cố định trên tường. Chúng ta cũng có thể cắm ổ cắm điện rời này vào một ổ cắm điện rời khác đang có điện

Trong nhà Nam hiện đang có n ổ cắm điện rời. Số lượng chỗ cắm trên mỗi ổ cắm điện này lần lượt là a1, a2, a3, ..., an chỗ cắm. Trên tường nhà Nam có một chỗ cắm cố định đang có điện. Vậy để cho một ổ cắm điện rời có điện thì phải cắm ổ cắm đó vào chỗ cắm cố định trên tường. Chúng ta cũng có thể cắm ổ cắm điện rời này vào một ổ cắm điện rời khác đang có điện. Dữ liệu vào: Dòng thứ nhất gồm 2 số nguyên n, m cách nhau một khoảng trắng, dữ liệu vào đảm bảo 1n, m10000, n là số lượng ổ cắm và m là số lượng thiết bị. Dòng thứ hai gồm n số nguyên a1, a2, a3, ..., an là số chỗ cắm trên các ổ cắm rời tương ứng, mỗi số cách nhau một khoảng trắng, dữ liệu vào đảm bảo 1ai50 . Dữ liệu ra: Là số nguyên cho biết số ổ cắm rời ít nhất cần sử dụng là bao nhiêu. Nếu đã sử dụng hết tất cả ổ cắm rời mà vẫn không đủ, in ra 1. Sample Input 1 3 4 3 2 2 Sample Output 1 2 Sample Input 2 4 7 3 3 2 4 Sample Output 2 3
1 Xem trả lời
Hỏi chi tiết
144
Tham khảo câu trả lời từ Trợ lý ảo Lazi
Để giải bài toán này, chúng ta cần xác định số ổ cắm điện rời tối thiểu cần sử dụng để có thể cắm đủ m thiết bị.

### Cách tiếp cận:

1. **Tính tổng số chỗ cắm**:
- Từ 1 ổ cắm cố định trên tường, số lượng ổ cắm rời sẽ cung cấp cho ta thêm chỗ cắm.
- Mỗi ổ cắm điện rời \( a_i \) không chỉ cắm thiết bị mà còn chiếm một chỗ cắm, vì vậy, số chỗ cắm khả dụng từ mỗi ổ rời là \( a_i - 1 \).

2. **Tính tổng chỗ cắm khả dụng**:
- Tổng chỗ cắm khả dụng từ tất cả các ổ rời sẽ là:
\[
\text{Total usable sockets} = \sum_{i=1}^{n} (a_i - 1) + 1
\]
Trong đó \( +1 \) là chỗ cắm cố định trên tường.

3. **Kiểm tra khả năng cắm đủ**:
- Nếu tổng số chỗ cắm khả dụng nhỏ hơn m, nghĩa là không đủ để cắm tất cả các thiết bị, và ta sẽ trả về -1.

4. **Tính số ổ cắm điện rời tối thiểu cần sử dụng**:
- Chúng ta sẽ tìm cách sử dụng tối thiểu số ổ cắm rời để đạt được ít nhất m chỗ cắm khả dụng.

### Cụ thể các bước thực hiện:

1. Nhập vào số ổ cắm điện rời n và số thiết bị cần cắm m.
2. Nhập vào danh sách số lượng chỗ cắm trên từng ổ cắm rời.
3. Tính tổng số chỗ cắm khả dụng.
4. Kiểm tra nếu tổng số chỗ cắm khả dụng lớn hơn hoặc bằng m.
5. Nếu có thể cắm đủ thiết bị, sắp xếp các ổ cắm theo số chỗ cắm giảm dần và tính số lượng ổ cắm điện rời cần dùng.

### Mã giả:

```python
def min_sockets_needed(n, m, a):
total_sockets = sum(a) - n + 1 # +1 for wall socket
if total_sockets < m:
return -1

a.sort(reverse=True) # Từ lớn đến nhỏ
current_sockets = 1 # Chỗ cắm từ ổ trên tường
used_sockets = 0

for sockets in a:
if current_sockets >= m:
break
current_sockets += (sockets - 1)
used_sockets += 1

return used_sockets if current_sockets >= m else -1

# Đọc dữ liệu đầu vào
n, m = map(int, input().split())
a = list(map(int, input().split()))

# Tính toán và xuất kết quả
result = min_sockets_needed(n, m, a)
print(result)
```

### Ví dụ minh họa:

- **Input**:
```
4 7
3 3 2 4
```
- **Output**: `3` (Cần tối thiểu 3 ổ cắm rời để cắm đủ 7 thiết bị).

Thông qua các bước trên, phương pháp này đảm bảo chúng ta có thể cắm đủ thiết bị một cách hiệu quả nhất.
2
0
Quỳnh Annh
23/08 17:55:47
+5đ tặng
#include<bits/stdc++.h>
using namespace std;
long long a[10005],i,s=0,x,n,k,m;
int main()
{
 ios_base::sync_with_stdio(0);
 cin>>n>>m;if(m==1){cout<<0;return 0;}
 for(i=1;i<=n;i++)
 {cin>>a[i];}
 sort(a+1,a+n+1);
 reverse(a+1,a+n+1);
 s=a[1];
 if(n==1 && s<m){cout<<-1;return 0;}
 if(s>=m){cout<<1;return 0;}
 for(i=2;i<=n;i++)
 {s=s+a[i]-1;
     if(s>=m){cout<<i;return 0;}
     if(s<m && i==n){cout<<-1;return 0;}
 }
}

Mở khóa để xem toàn bộ nội dung trả lời

(?)
Bạn đã đạt đến giới hạn của mình. Bằng cách Đăng ký tài khoản, bạn có thể xem toàn bộ nội dung trả lời
Cải thiện điểm số của bạn bằng cách đăng ký tài khoản Lazi.
Xem toàn bộ các câu trả lời, chat trực tiếp 1:1 với đội ngũ Gia sư Lazi bằng cách Đăng nhập tài khoản ngay bây giờ
Tôi đã có tài khoản? Đăng nhập

Bạn hỏi - Lazi trả lời

Bạn muốn biết điều gì?

GỬI CÂU HỎI
Học tập không giới hạn cùng học sinh cả nước và AI, sôi động, tích cực, trải nghiệm

Hôm nay bạn thế nào? Hãy nhấp vào một lựa chọn, nếu may mắn bạn sẽ được tặng 50.000 xu từ Lazi

Vui Buồn Bình thường
×
Trợ lý ảo Trợ lý ảo
×
Đấu trường tri thức | Lazi Quiz Challenge +500k
Gửi câu hỏi
×