題目
小A班的 n 位小朋友在操場圍坐成一圈，每人手里有數量不等的糖果，小朋友們可以向左右傳遞，請問至少需要傳遞多少顆糖果才能使得所有小朋友手里的糖果數一樣，
輸入
第一行輸入一個正整數n，表示小朋友的個數，（1≤n≤1000000 ）
接下來n行，每行一個整數，表示每個小朋友最開始自己手里的糖果數，
輸出
一個整數，表示最少傳遞的糖果數，（資料保證有解）
輸入樣例
4
1
2
5
4
輸出樣例
4
思路：
原本以為是個水題，然后沒看資料點就直接暴力列舉，然后就
正解：
打表AC 貪心思想,首先求出總數/n(個數)，在利用類似前綴和思想將結果存在一個陣列里，排序后求出中值，在用每個數和中值相減即可，
代碼
#include<bits/stdc++.h>
using namespace std;
long long a[1000100],x[1000100];
long long mid,ans,n,sum;
int main()
{
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
sum+=a[i];
}
sum/=n;
for(int i=1;i<=n;i++)
x[i]=x[i-1]-a[i]+sum;
sort(x+1,x+1+n);
mid=x[(n+1)/2];
for(int i=1;i<=n;i++)
ans+=abs(x[i]-mid);
cout<<ans;
return 0;
}
本蒟蒻第一次寫題解，求大佬們多多關照
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/257821.html
標籤：其他
上一篇：PackageManagerService啟動詳解(三)之BOOT_PROGRESS_PMS_START流程分析