fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. int a[5],n,cnt;
  5. /* n: số lượng nhóm
  6.   cnt: số lượt trình diễn ít nhất
  7.   a[5]: đánh số từ 1 đến 4, A_i là số lượng nhóm có i thành viên (0<i<5)
  8. */
  9. int main() {
  10. freopen("AODAI.INP","r",stdin);
  11. freopen("AODAI.OUT","w",stdout);
  12. // nhập xuất file theo đề bài
  13. ios::sync_with_stdio(false);
  14. cin.tie(0), cout.tie(0);
  15. cin >> n;
  16. for(int i=1;i<=n;i++) {
  17. int x; cin >> x;
  18. a[x]++;
  19. // nhập vào n nhóm và cộng A_x lên một đơn vị mỗi khi gặp nhóm có x thành viên
  20. }
  21. cnt=a[4]; // nhóm nào có 4 thành viên thì không thể kết hợp thêm nhóm khác nên cnt = a[4] luôn
  22. cnt+=a[3], a[1]-=a[3]; // nhóm 3 kết hợp được với nhóm 1 (3+1 = 4) nên cnt += a[3]
  23. // đồng thời nhóm 1 cũng phải trừ đi số lượng nhóm 3 bởi vì mỗi nhóm 3 đã kết hợp với 1 nhóm 1 rồi
  24. cnt+=a[2]/2; // nhóm có 2 thành viên thì ta có thể ghép 2 nhóm 2 lại (2+2 = 4) nên cnt += a[2]/2 (lấy nguyên)
  25. if(a[2]%2!=0) cnt+=1,a[1]-=2; // nếu a[2] là số lẻ thì cnt += 1 và nhóm 1 trừ 2 đơn vị
  26. // bởi vì nhóm 2 còn lại (do ở trên ghép 2 nhóm 2 một lần) sẽ kết hợp với 2 nhóm 1
  27. if(a[1]>0) {
  28. // nếu a[1] > 0 thì tính bởi vì ở trên sau khi nhóm 1 bị trừ thì có thể âm hoặc = 0
  29. cnt+=a[1]/4; // kết hợp 4 nhóm 1 lại một lần (1+1+1+1 = 4) nên cnt += a[1]/4 (lấy nguyên)
  30. if(a[1]%4!=0) cnt+=1; // nếu a[1] không chia hết cho 4 có nghĩa là
  31. // sau khi kết hợp 4 nhóm 1 thành 1 nhóm thì còn dư lại một phần < 4 nên ta phải cnt += 1
  32. }
  33. cout << cnt;
  34. return 0;
  35. }
Success #stdin #stdout 0s 5308KB
stdin
6
4 1 2 3 2 3
stdout
Standard output is empty