Đề 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:
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- int main(){
- ll n,m;
- cin>>n>>m;
- ll res_min, res_max,du,thuong;
- if(m==1){
- res_min=res_max=n*(n-1)/2;
- cout<<res_min<<" "<<res_max;
- return 0;
- }
- du=n%m;
- thuong=n/m;
- // res_min=thuong*(thuong-1)*(m-1)/2 + (thuong+du)*(thuong+du-1)/2;
- res_min=du*(thuong+1)*thuong/2 + (m-du)*(thuong)*(thuong-1)/2;
- n-=(m-1);
- res_max = n*(n-1)/2;
- cout<<res_min<<" "<<res_max;
- return 0;
- }
Không có nhận xét nào:
Đăng nhận xét