题解：P13457 [GCJ 2008 #1A] Minimum Scalar Product

xyx404 · 2025-07-26 08:57:42 · 题解

简要题意：

给定两个 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。

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

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

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

故代码正确。