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:
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- int main(){
- ll t,n,k,res;
- scanf("%lld",&t);
- while(t--){
- vector<ll> res;
- scanf("%lld",&n);
- ll num=0,sum=0;
- for(int i=0;i<n;i++){
- scanf("%lld",&num);
- sum+=num;
- res.push_back(num);
- }
- ll ave =sum/n;
- ll sum3 = n*ave;
- ll c1=0,c2=0;
- for(int i=0;i<n;i++){
- if(res[i]>ave){
- c2=c2+res[i]-ave;
- }
- else{
- c1=c1+ave-res[i];
- }
- }
- printf("%lld\n",c2);
- }
- return 0;
- }
Không có nhận xét nào:
Đăng nhận xét