题解 AT2019 【いっしょ / Be Together】
encore
2018-09-28 20:29:46
这个题目最最最坑的地方在于题目描述。第四组样例里没有输出。然后我就莫名其妙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。