Thứ Sáu, 13 tháng 11, 2020

Bài toán đếm số phép toán tối thiểu để cho mảng có các phần tử bằng nhau

 Nguồn: $\href{https://zoj.pintia.cn/problem-sets/91827364500/problems/91827370513}{Đây}$

Tóm tắt: Cho một mảng gồm n phần tử và có 2 phép toán:

+ Chọn một phần tử khác không và sau đó giảm nó đi 1 đơn vị

+ Chọn 1 một phần tử khác không giảm nó 1 đơn vị và chuyển 1 đơn vị này đến 1 phần tử khác của mảng đó

Yêu cầu: Hỏi ta cần ít nhất bao nhiêu phép toán để mảng trên có các phần tử bằng nhau

Lời giải: + Implementation bằng cách ta tính trước phần nguyên của giá trị trung bình các phần tử trong mảng, sau đó thực hiện if else cộng trừ.

Source:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. int main(){
  5. ll t,n,k,res;
  6. scanf("%lld",&t);
  7. while(t--){
  8. vector<ll> res;
  9. scanf("%lld",&n);
  10. ll num=0,sum=0;
  11. for(int i=0;i<n;i++){
  12. scanf("%lld",&num);
  13. sum+=num;
  14. res.push_back(num);
  15. }
  16. ll ave =sum/n;
  17. ll sum3 = n*ave;
  18. ll c1=0,c2=0;
  19. for(int i=0;i<n;i++){
  20. if(res[i]>ave){
  21. c2=c2+res[i]-ave;
  22. }
  23. else{
  24. c1=c1+ave-res[i];
  25. }
  26. }
  27. printf("%lld\n",c2);
  28. }
  29. return 0;
  30. }

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ự...