题解 AT2019 【いっしょ / Be Together】

encore

2018-09-28 20:29:46

Solution

这个题目最最最坑的地方在于题目描述。第四组样例里没有输出。然后我就莫名其妙wa了三四个点。**其实就算答案是0也要输出的。**这还是我改的时候失误发现的。~~所以我交了6次才过~~ 好了不多说,上代码: ```cpp #include<iostream> #include<cmath> #define f(x) (x)*(x) using namespace std; int n; int a[1001]; int cnt; int ans; int tt=0x7fffffff; int main() { cin>>n; int mi=tt,ma=-tt; for(int i=1;i<=n;i++) { cin>>a[i]; cnt+=a[i]; if(a[i]<mi) mi=a[i]; if(a[i]>ma) ma=a[i]; } int t=cnt/n; for(int k=mi;k<=ma;k++) { ans=0; for(int i=1;i<=n;i++) { ans+=f(a[i]-k); } if(ans<tt) tt=ans; } cout<<tt; return 0; } ``` 这个其实很好想:要改就在a数组的最大值和最小值之间选一个数改。数据那么水,暴力枚举不就好了。 当然还有一个技巧型的代码: ```cpp #include<iostream> #include<cmath> #define f(x) (x)*(x) using namespace std; int n; int a[1001]; int cnt; int ans; int ans2; int ans3; int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; cnt+=a[i]; } int t=cnt/n; for(int i=1;i<=n;i++) { ans+=f(a[i]-t); ans2+=f(a[i]-t-1); ans3+=f(a[i]-t+1); } int tt=ans<ans2? ans:ans2; tt=tt>ans3? ans3:tt; cout<<tt; return 0; } ``` 原理的话很玄学。你可以试试看画一个函数~~或者凭直觉~~发现只可能是平均值和离平均值最近的两个点这三个点。 ~~其实这本来就是一道考循环嵌套的水题,钻深了不要得不偿失~~ 以上代码均AC。