二分贪心——U

xiaoxiao2021-02-27  156

题目要求:

小鲍勃喜欢和他的砖块一起玩。他将砖块放在另一块上,并建立不同高度的堆垛。“看,我已经建了一堵墙!”他告诉他的姐姐爱丽丝。“呵呵,你应该把所有的堆叠都一样高,然后你会有一个真正的墙壁。”她反驳道。经过一番考虑后,鲍勃看到她是对的。所以他开始重新排列砖块,一个接一个,所有的堆叠都是相同的高度。但是,由于鲍勃懒惰,他想用最少数量的砖块来做到这一点。你能帮我吗? 

题目思路: 要找最少移动数,就只要把大于平均数的数,给小于平均数的数匀几个。所以只要求出大于平均数的数减去平均数的和就能求出最小移动数。 细节处理 几个量的初值应该在while内赋值,防止错误答案。 #include<iostream> using namespace std; int main() { int n,i,j,N=0; int k[100]={0}; while(cin>>n) { if(n==0)break;int sum=0,s=0,a[50]; for(i=0;i<n;i++) {cin>>a[i]; s=s+a[i];} sum=s/n; for(i=0;i<n;i++) {if(a[i]>sum) k[N]+=a[i]-sum;} N++;} for(i=0;i<N;i++) { cout<<"Set #"<<i+1<<endl; cout<<"The minimum number of moves is "<<k[i]<<"."<<endl; cout<<endl;} return 0; } 感悟:注意赋值位置的问题,注意细节处理。
转载请注明原文地址: https://www.6miu.com/read-16088.html

最新回复(0)