2016 Multi-University Training Contest 2-1001---HDU 5734 Acperience

本文主要是介绍2016 Multi-University Training Contest 2-1001---HDU 5734 Acperience，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

• 题目链接：HDU 5734
• 题意：有一个向量：$W=(w_1,w_2,...,w_n)$，求一个数$\alpha(\alpha \ge 0)$和一个$B=(b_1,b_2,...,b_n)$向量，使得$\left\| W - \alpha B \right\|^2$的值最小。
  注：$\left\| X \right\|=\sqrt {x_{1}^{2}+\cdots +x_{n}^{2}}$，其中$X = (x_1, x_2, ..., x_n)$，其实就是向量的模长。
• 题解：
  官方题解：
  展开式子可以得到： $$\left| W-\alpha B \right|^2=\displaystyle\alpha^2\sum_{i=1}^{n}b_i^2-2\alpha\sum_{i=1}^n{w_ib_i}+\sum_{i=1}^{n}w_i^2$$
  由于$b_i\in {+1,-1}$那么$\displaystyle\sum_{i=1}^{n}b_i^2=n$, 显然$c=\displaystyle\sum_{i=1}^{n}w_i^2$​​ 也是常数. 转化成求$\displaystyle\alpha^2n-2\alpha\sum_{i=1}^n{w_ib_i}+c$的最小值.
  对于固定的$\alpha \ge 0$, 只要$\displaystyle\sum_{i=1}^n{w_ib_i}$​最大就好了. 显然$b_i=sign(w_i)$(符号函数)的时候, $\displaystyle\sum_{i=1}^n{w_ib_i}=\sum_{i=1}^{n}|w_i|$最大.
  进一步的, 上面显然是一个关于\alphaα的二次方程, 于是当$\alpha=\frac{1}{n}\displaystyle\sum_{i=1}^n{w_ib_i}=\frac{1}{n}\displaystyle\sum_{i=1}^{n}{|w_i|}$时, 取到最大值.
  化简下, 可以得到最小值是$\sum_{i=1}^n{w_i^2}-\frac{1}{n}(\displaystyle\sum_{i=1}^{n}|w_i|)^2$.
  代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int MAX=100000+10;
int a[MAX];
int main()
{//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);int T;scanf("%d",&T);while(T--){int n;scanf("%d",&n);LL sum1=0,sum2=0;for(int i=0;i<n;i++){scanf("%d",&a[i]);sum1+=1ll*a[i]*a[i];sum2=sum2+abs(a[i]);}LL gcd=__gcd(sum2*sum2,(LL)n);cout<<sum1*n/gcd-sum2*sum2/gcd<<"/"<<n/gcd<<endl;}return 0;
}

这篇关于2016 Multi-University Training Contest 2-1001---HDU 5734 Acperience的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---