↓ 跳过正文
题解：P13457Minimum Scalar Product

题解：P13457Minimum Scalar Product

xyx404
作者
xyx404
Have a nice day.
目录

封面

{% link 洛谷文章链接,xyx404,https://www.luogu.com.cn/article/9jwfekli %}

简要题意：
#

给定两个 vector，$v_1 = (x_1, x_2, \cdots, x_n)$ 和 $v_2 = (y_1, y_2,\cdots, y_n)$，要求最小化标量积 $x_1 \times y_1 + x_2 \times y_2+ \cdots + x_n \times y_n$，两个 vector 中的元素可以任意更改位置。

思路：
#

将 $v_1$ 和 $v_2$ 分别按升序和降序进行排序，然后计算即可。

证明在最后。

代码：
# 

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define itn int
#define ull unsigned long long
int T;
LL a[810],b[810];
int cnt;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--){
        cnt++;
        int n;cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=1;i<=n;i++)cin>>b[i];
        sort(a+1,a+1+n);
        sort(b+1,b+1+n);
        LL ans=0;
        for(int i=1,j=n;i<=n;i++,j--){
            ans+=a[i]*b[j];
        }
        cout<<"Case #"<<cnt<<": "<<ans<<"\n";
    }
    return 0;
}

证明：
#

尽管比较显然，但我们还是证明一下，考虑反证法。

假设存在另一种配对方式，使得标量积比 $v_1$ 升序，$v_2$ 降序的配对方式更小。

设 $v_1$ 按升序排序 $x_1 \le x_2 \le \cdots \le x_n$，$v_2$ 降序排序 $y_1 \ge y_2 \ge \cdots y_n$，这样的标量积为 $S_1 = x_1 \times y_1 + x_2 \times y_2 + \cdots + x_n \times y_n$。

假设存在另一种配对方式，存在两个位置 $i$ 和 $j$，$x_i$ 和 $y_j$ 配对，$x_j$ 和 $y_i$ 配对，且这种配对的标量积 $S_2 < S_1$，则需要满足 $x_i \times y_i + x_j \times y_j > x_i \times y_j + x_j \times y_i$。

考虑两种配对方式带来的差异：

  • $x_i$ 和 $y_i$ 配对，$x_j$ 和 $y_j$ 配对，和为 $x_i \times y_i + x_j \times y_j$。
  • $x_i$ 和 $y_j$ 配对，$x_j$ 和 $y_i$ 配对，和为 $x_i \times y_j + x_j \times y_i$。

我们计算差值，以此比较大小：

作差法

因此，不存在比 $v_1$ 升序，$v_2$ 降序的配对方式更小的标量积。

故代码正确。