Thứ Ba, 24 tháng 11, 2020

Cho n học sinh, được chia vào m nhóm (n>=m) sao cho mỗi nhóm ít nhất một người. Biết rằng những người thuộc vào một nhóm sẽ quen biết nhau. Hỏi có tối đa bao nhiêu cặp quen nhau và tối thiểu cặp quen nhau trong tất cả cách xếp !

 Đề bài: $\href{https://codeforces.com/problemset/problem/478/B}{Đây}$

Tóm tắt: Cho n học sinh, được chia vào m nhóm (n>=m) sao cho mỗi nhóm ít nhất một người. Biết rằng những người thuộc vào một nhóm sẽ quen biết nhau. Hỏi có tối đa bao nhiêu cặp quen nhau và tối thiểu cặp quen nhau trong tất cả cách xếp !

Lời giải: Ở đây, ta chỉ cần nghĩ gì làm nấy, suy nghĩ chậm rãi, tính từng testcase góc là được

Source:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. int main(){
  5. ll n,m;
  6. cin>>n>>m;
  7. ll res_min, res_max,du,thuong;
  8. if(m==1){
  9. res_min=res_max=n*(n-1)/2;
  10. cout<<res_min<<" "<<res_max;
  11. return 0;
  12. }
  13. du=n%m;
  14. thuong=n/m;
  15. // res_min=thuong*(thuong-1)*(m-1)/2 + (thuong+du)*(thuong+du-1)/2;
  16. res_min=du*(thuong+1)*thuong/2 + (m-du)*(thuong)*(thuong-1)/2;
  17. n-=(m-1);
  18. res_max = n*(n-1)/2;
  19. cout<<res_min<<" "<<res_max;
  20. return 0;
  21. }

Không có nhận xét nào:

Đăng nhận xét

Cho mảng A gồm n phần tử, sắp xếp lại mảng này sao cho số cặp a[i] bé hơn a[i+1] lớn nhất có thể

 Đề bài: $\href{https://codeforces.com/problemset/problem/651/B}{Đây}$  Tóm tắt:Cho một mảng gồm n phần tử, hãy sắp xếp lại mảng theo thứ tự...