Bình luận

• 
  

  0

  trinhhcuongday    11:52 p.m. 16 Tháng 11, 2024

  ý tưởng tham khảo nè:
  chặt nhị phân nhé
  ban đầu cho l=1 và r =tổng các phần tử là số kẹo của tùng vị
  dùng 1 hàm kiểm tra là (số kẹo + k - 1)/ k với k là mức độ ghen tị
  đủ để chia cho n em thì r=mid-1, ngược lại là l=mid+1 cứ thế tìm và trả về giá trị nỏ nhất tìm được
  code tham khảo:

  include <bits/stdc++.h>

  using namespace std;

  bool check(vector<int> &keo, int n, long long maxn) {
  long long daco = 0;
  for (int candy : keo) {
  daco += (candy + maxn - 1) / maxn; // Tương đương ceil(candy / maxn)
  if (daco > n) return false; // Nếu vượt quá số trẻ, trả về false
  }
  return true;
  }

  long long nhonhat(vector<int> &keo, int n) {
  long long l = 1, r = accumulate(keo.begin(), keo.end(), 0LL);
  long long kq = r;

  while (l <= r) {
      long long mid = (l + r) / 2;
      if (check(keo, n, mid)) {
          kq = mid; // Cập nhật kết quả
          r = mid - 1;  // Thử mức ghen tị nhỏ hơn
      } else {
          l = mid + 1;  // Tăng mức ghen tị
      }
  }
  return kq;
  

  }

  int main() {
  int n, m;
  cin >> n >> m;
  vector<int> keo(m);
  for (int i = 0; i < m; i++) {
  cin >> keo[i];
  }
  cout << nhonhat(keo, n) << endl;
  return 0;
  }

  1 phản hồi
• 
  

  2

  blinh    11:48 p.m. 9 Tháng 9, 2024 ← chỉnh sửa 6 →

  summary

  hint: sử dụng tìm kiếm nhị phân rồi xét kết quả
  vd:
  5 2
  4
  7
  sử dụng định lý dirichlet nếu
  -mức độ ghen tị là 3 thì ta có thể chia: AAA, A, BBB, BBB, B => thỏa
  -mức độ ghen tị là 4 thì ta có thể chia: AAAA, BBBB, BBB (còn dư 2 đứa :v) => loại => xét đến kết quả thấp hơn
  -mức độ ghen tị là 2 thì ta có thể chia: AA, AA, BB, BB (còn dư 3 cái kẹo còn lại) => loại => xét kết quả cao hơn

  CODE AC PYPY(PYTHON)

  a,b=map(int,input().split())
  ds=[]
  res=-1
  for i in range(b):ds.append(int(input()))
  l,r=1,int(max(ds))
  def check(n):
      ans=0
      for i in ds:
          t=i//n
          if t<i/n:t+=1
          ans+=t
      if ans<=a:return True
      else:return False
  while l<=r:
      mid=(l+r)//2
      if check(mid):
          res=mid
          r=mid-1
      else:l=mid+1
      #print(mid)
  print(res)
  

• 
  

  0

  hien18086    3:04 p.m. 25 Tháng 8, 2024

  lý ra đề phải nói rõ có chia hết kẹo hay không chứ

• 
  

  0

  nd24052009    7:23 a.m. 25 Tháng 5, 2024

  Ai cho mình xin ý tưởng bài này với ạ