CHONGACH - Chồng Gạch
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
0.3s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
Hùng có N viên gạch được đánh số từ 1 đến N. Các viên gạch có độ cứng lần lượt là a1,a2,...,an. Một viên gạch có độ cứng x nghĩa là Hùng có thể chồng lên trên viên gạch đó tối đa x viên gạch khác, nếu chồng nhiều hơn thì viên gạch đó bị vỡ.
Hỏi Hùng có thể sắp được chồng gạch cao nhất là bao nhiêu viên?
Input
* Dòng đầu tiên là số nguyên N- là số viên gạch.(~ 1 \le N \le 100000 ~)
* N dòng tiếp theo gồm N số nguyên không âm(~ 0 \le a_i \le 100000 ~)
Output
Số nguyên xác định chiều cao cao nhất của chồng gạch mà Hùng sắp được.
Sample
Input #1
5
1
2
3
4
5
Output #1
5
Problem source: THCS Lập Thạch
Bình luận
include <bits/stdc++.h>
using namespace std; int main() { int n; cin >> n; int a[n]; for(int i = 0; i < n; i++) cin >> a[i]; sort(a, a + n); reverse(a, a + n); if(a[0] >= n - 1) cout << n; else{ int h = 0; while(true){ if(h >= a[0]) break; h++; } cout << h; } return 0; }
Cố gắng hết sức rồi mới xem giải thích nhé.
Ý tưởng bài này như sau: Trước tiên sort lại cái đống gạch đã và ta đặt chỉ số gạch bắt đầu từ 1 -> n
TH1: Nếu viên gạch to nhất mà >= số gạch (ví dụ n = 5, amax = 10 => n < amax), thì in luôn ra số gạch (n) vì nhiều lắm cũng chỉ có n viên để xếp thôi mà => chiều cao = n
TH2: Viên gạch to nhất < n, ví dụ n = 6, đống gạch của ta như sau: 1 1 1 1 3 5, thì ta thực hiện các bước sau:
đặt độ cứng tối đa được phép là x = amax (ở ví dụ thì là x = 5) và h là chiều cao (h = 0), sau đó ta cứ x -= 1 khi nhích lên (h += 1). Tuy nhiên, nếu viên gạch tiếp theo mà có độ cứng nhỏ hơn độ cứng hiện tại thì phải đặt lại x = độ cứng mới đó (ở ví dụ sẽ là: từ x = 5 -> x = 3), rồi lại x -= 1 khi nhích lên (h += 1).
Đến đây nếu độ cứng của ta = 0 trước khi chạy hết đống gạch thì ta sẽ h += 1 viên nữa rồi break. Ngược lại thì không cần cộng.
ở ví dụ ta thấy x = 3 -> x = 1 sau đó trừ đi 1 và break ra, tuy nhiên do chưa đi hết dãy (trước đó chắc chắn sẽ có viên có độ cứng <= độ cứng x hiện tại. Ta thấy vẫn có thể để thêm 1 viên lên nữa) nên ta h += 1 rồi mới break.
CƯỜNG GIẢ HỌ ĐINH. VẠN CỔ TỐI CƯỜNG
include <iostream>
include <vector>
include <algorithm>
using namespace std;
int main() { int a; cin >> a;
} Day la code cua mik dua vao y tuong cua bn tren full ac.
// Đã xoá commet
#include <bits/stdc++.h>
using namespace std; int main() { long long n; cin >> n; long long a[n + 1]; a[0] = 0; for (long long i = 1; i <= n; i++) cin >> a[i]; sort(a, a + n + 1);
long long d = a[n]; long long h = 0; if (n <= a[n]) cout << n; else { for (long long i = n; i >= 1; i--) { if(a[i] < d) d = a[i]; d -= 1; h += 1; if (d == 0) { if (i > 1) h += 1; break; } } cout << h; } }
admin để sai category rồi =))) bài này dễ quá bọn e kh làm đc =))))))
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.