2019-07-20 09:23 已编辑字节跳动_后台开发

关注

2019年牛客多校C题Euclidean Distance

https://ac.nowcoder.com/acm/contest/881/C

题目链接

题意

给你 $n$ 个数 $a_i$ ，要你在满足下面条件下使得 $\sum\limits_{i=1}^{n}(a_i-p_i)^2$ 最小（题目给的 $m$ 只是为了将 $a_i$ 变成一个整数，那么我们就当此处的 $p_i$ 扩大为题目给的 $m$ 倍，然后把 $m$ 放到分母去，以下不再解释）：

$p_i\in\mathbb{R}$ ；
$p_i\geq 0,i\in[1,n]$ ；
$\sum\limits_{i=1}^{n}p_i=m$ 。

思路

由于叉姐的题解太高深了，本菜鸡完全看不懂(爆哭)，因此我们从其他角度来求解本题。
首先根据题目要求的式子和条件可以发现我们能做的只是将 $p_i$ 合理赋值使得 $\sum\limits_{i=1}^{n}(a_i-p_i)^2$ 最小，且 $a_i\in[-m,m],p_i\in[0,m]$ ，那么 $p_i$ 只能将 $a_i$ 的值不断减小而不能增加(即使 $a_i<0$ )，因此我们就可以通过调节 $p_i$ 的值使得 $a_i$ 的最大值尽可能的小，且 $\sum\limits_{i=1}^{n}p_i=m$ 。
假设我们进行处理前 $i-1$ 后 $p$ 的和还剩下 $las$ ，前 $i$ 个的 $a$ 的值都已经被削到了 $a_i$ ，那么：

如果 $i\times|(a[i+1]-a[i])|\leq las$ ，那么 $las=las-i\times|(a[i+1]-a[i])|$ ；
否则，就记录这个位置为 $idx$ ，并且 $break$ （ $idx$ 的初始值为 $n$ ）。

其中的 $idx$ 就是说我们可以通过调节 $p_i$ 的值使得前 $idx$ 个数都相等且等于 $a_{idx}-\frac{las}{idx}$ ，因此最后答案是 $\frac{idx\times(a_{idx}-\frac{las}{idx})^2+\sum\limits_{i=idx+1}^{n}a_{idx}^2}{m^2}$ (因为我们最初始时将 $a_i,p_i$ 都扩大了 $m$ 倍，将 $m$ 丢到了分母)。
如果没看懂我们可以通过分析样例 $3$ 来帮助理解：
首先我们将 $a$ 数组排序得到:
$3$ $1$ $-2$

处理前 $1$ 个数，此时 $las=10>1\times|1-3|=2$ ，于是我们将 $a_1$ 变成 $1$ ， $las$ 消耗 $2$ ；
处理前 $2$ 个数，此时 $las=8>2\times|-2-1|=6$ ，于是我们将 $a_1,a_2$ 变成 $-2$ ， $las$ 消耗 $6$ ；
处理前 $3$ 个数，此时 $las=2,a_1=a_2=a_3=-2$ ，由于 $las$ 最后要变成 $0$ 且 $a_i$ 的最大值要尽可能小，那么我们需要均匀分配，所以最后 $a_1=a_2=a_3=-2-\frac{2}{3}=-\frac{8}{3}$ 。

所以最后答案为 $\frac{(-\frac{8}{3})^2\times 3}{10\times 10}=\frac{16}{75}$ 。 $update$ ：

证明这个写法的正确性：

假设现在有两个数 $a,b(a\geq b)$ ，总的可以减少的数量为 $m$ 。

1.首先证明当 $a-b\geq m$ 时全放在 $a$ 上最优：

设 $m$ 中有 $x(1\leq x\leq m)$ 用在 $b$ 上，那么和为 $(a-m+x)^2+(b-x)^2$ ，全用在 $a$ 上的话和为 $(a-m)^2+b^2$ ，两者做差：

$\begin{aligned} &(a-m+x)^2+(b-x)^2-(a-m)^2-b^2&\\ =&(a-m)^2+2x(a-m)+x^2+b^2-2bx+x^2-(a-m)^2-b^2&\\ =&2x^2+2x(a-m)-2bx&\\ =&2x^2+2x(a-b-m)\geq 0& \end{aligned}$

2.再证明当 $a=b,m\geq 0$ 时均分最优：

设 $m$ 中有 $x(1\leq x< \frac{m}{2})$ 用在 $b$ 上，那么和为 $(a-m+x)^2+(b-x)^2$ ，将其化简：

$\begin{aligned} &(a-m+x)^2+(b-x)^2&\\ =&(a-m)^2+2(a-m)x+x^2+b^2-2bx+x^2&\\ =&(a-m)^2+b^2+2x^2+2(a-m-b)x&\\ =&(a-m)^2+b^2+2(x^2-mx)(\text{题目给定的}a=b)& \end{aligned}$

由于前一半和 $x$ 无关，而后一半 $x^2-mx=(x-\frac{m}{2})^2-\frac{m^2}{4}$ 在 $x=\frac{m}{2}$ 时取最小值。

最后我们来讨论有 $n$ 个数分配 $m$ ，其中 $a,b$ 分别为 $n$ 个数中的最大和次大值时为什么当 $m>a-b$ 时每次将最大值减小到次大值是最优的的情况：

$(1).$ 首先如果将 $m$ 全部减到一个数上，那么肯定是减小最大值是最优的： $(a-m)^2+c^2-a^2-(c-m)^2=a^2-2am+m^2+c^2-a^2-c^2+2cm-m^2=2m(c-a)<0(c$ 为剩余 $n-1$ 个数中的任意一个数)；
$(2).$ 如果分配到两个数上那么也一定时分到最大值和次大值上，理由同上；那么此时我们应该怎么分配最优呢？我们发现当 $a$ 减少到 $a=b$ 之后如果再减少 $a$ 的话， $b$ 就已经大于 $a$ 成为新的最大值了，那么再减小 $a$ 肯定不是最优解(理由为 $(1)$ )，因此只能将最大值 $a$ 减小到次大值 $b$ ，然后根据上面的 $2$ 得知均匀分配最优；
分配到任意多个数的情况基本和 $(2)$ 相同。

因此我们可以得知本题的解决策略是正确的。
(如果想法或者证明过程有错误，还请各位大佬指正~)

代码实现如下

#include <set>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;

typedef long long LL;
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pLi;
typedef pair<int, LL> pil;;
typedef pair<int, int> pii;
typedef unsigned long long uLL;

#define lson rt<<1
#define rson rt<<1|1
#define lowbit(x) x&(-x)
#define name2str(name) (#name)
#define bug printf("*********\n")
#define debug(x) cout<<#x"=["<<x<<"]" <<endl
#define FIN freopen("D://Code//in.txt","r",stdin)
#define IO ios::sync_with_stdio(false),cin.tie(0)

const double eps = 1e-8;
const int mod = 1000000007;
const int maxn = 1e5 + 7;
const double pi = acos(-1);
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3fLL;

int n, m;
int a[maxn];

int main() {
#ifndef ONLINE_JUDGE
FIN;
#endif // ONLINE_JUDGE
    while(~scanf("%d%d", &n, &m)) {
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &a[i]);
        }
        sort(a + 1, a + n + 1, [](int a, int b){return a > b;});
        int idx = n;
        int las = m;
        for(int i = 1; i < n; ++i) {
            if(i * abs(a[i+1] - a[i]) > las) {
                idx = i;
                break;
            } else {
                las -= i * abs(a[i+1] - a[i]);
            }
        }
        LL num1 = 1LL * (idx * a[idx] - las) * (idx * a[idx] - las);
        LL num2 = 1LL * idx * m * m;
        for(int i = idx + 1; i <= n; ++i) {
            num1 += 1LL * a[i] * a[i] * idx;
        }
        LL tmp = __gcd(num1, num2);
        num1 /= tmp, num2 /= tmp;
        if(num2 == 1) printf("%lld\n", num1);
        else printf("%lld/%lld\n", num1, num2);
    }
    return 0;
}