HLG2081分苹果
生活随笔
收集整理的這篇文章主要介紹了
HLG2081分苹果
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
| 蘋果 | ||||||
| ||||||
| Description | ||||||
| 圓桌旁圍坐n個人，按順序?qū)⑺麄兙幪枮?span style="font-size:12pt;">1~n，第i個人有xi個蘋果(i=1,2,...,n）。蘋果的總數(shù)量為A。數(shù)據(jù)保證A為n的倍數(shù)，且v=A/n。 每個人可以給左右相鄰的人蘋果，直到每個人手上的蘋果數(shù)為平均值v。 輸出需要轉(zhuǎn)移的蘋果數(shù)量的最小值。 | ||||||
| Input | ||||||
| 有多組測試數(shù)據(jù)。 每組測試數(shù)據(jù)的第一行為正整數(shù)n（n<=10^6），接下來有n行，每行一個整數(shù)，逆時針給出初始狀態(tài)每人手中的蘋果數(shù)xi。 處理到文件結(jié)束。 | ||||||
| Output | ||||||
| 對每組測試數(shù)據(jù)，輸出轉(zhuǎn)移蘋果數(shù)量的最小值，每組一行。數(shù)據(jù)保證輸出為64位無符號整數(shù)范圍內(nèi)。 | ||||||
| Sample Input | ||||||
| 3 100 100 100 4 1 2 5 4 | ||||||
| Sample Output | ||||||
| 0 4 | ||||||
| Source | ||||||
| "科林明倫杯"哈爾濱理工大學(xué)第四屆ACM程序設(shè)計競賽（預(yù)選賽） |
?
?
?
?
?
?
?
| #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; /* 能兩邊給，那么x1可以給x2，x2也可給x1，絕對值就是|x1-x2|，我們假設(shè)逆時針順序x2給x1，就相當(dāng)于x2給了x1了a2（a2正負(fù)都OK）個蘋果，那個x1就有：A1+a2-a1=m,A2+a3-a2=m...... a2=m-A1+a1 a3=m-A2+a2=2m-A1-A2+a1 a4=3m-A1-A2-A3+a1....... 由于A1，A2和m都是給定的，所以影響的只有a，也就是指a1. Ci指Ai-M 那么a2=a1-C1,a3=a1-C2,a4=a1-C3 使ai的絕對值最小，則轉(zhuǎn)換成一條直線上的點到某點上的距離之和最小的問題 則a1為這些數(shù)的中位數(shù) */ int A[1000001],C[1000001]; int main() { int n,sum; while(~scanf("%d",&n)){ long long int sum=0; for(int i=1;i<=n;i++) { scanf("%d",&A[i]); sum+=A[i]; } int v=sum/n; /*計算Ci，寫寫方程代代看看*/ C[0]=0; for(int i=1;i<=n;i++) { C[i]=A[i]-v+C[i-1]; } /*求和*/ sort(C+1,C+1+n); long long int s=0; for(int i=1;i<=n/2;i++) { s=s+C[n+1-i]-C[i]; } printf("%lld\n",s); } return 0; } | ||
|
?
?
?
?
?
?
| #include<stdio.h> #include<string.h> #include<iostream> #include<math.h> #include<algorithm> using namespace std; int a[1000005],c[1000005]; int main() { int n; while(scanf("%d",&n)!=EOF) { long int sum=0; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); sum=sum+a[i]; } int m=sum/n; c[0]=0; for(int i=1;i<=n;i++) c[i]=m+c[i-1]-a[i]; sort(c+1,c+n+1); long int num=0; int temp=c[n/2+1]; for(int i=1;i<=n;i++) { num=num+abs(c[i]-temp); } printf("%ld\n",abs(num)); } return 0; } | ||
|
?
轉(zhuǎn)載于:https://www.cnblogs.com/13224ACMer/p/4422496.html
總結(jié)
以上是生活随笔為你收集整理的HLG2081分苹果的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Word字体与像素的对应关系(转)
- 下一篇： 中文分词词性对照表（转）