题解:P13457Minimum Scalar Product

封面

简要题意:

给定两个 vector,v1=(x1,x2,,xn)v_1 = (x_1, x_2, \cdots, x_n)v2=(y1,y2,,yn)v_2 = (y_1, y_2,\cdots, y_n),要求最小化标量积 x1×y1+x2×y2++xn×ynx_1 \times y_1 + x_2 \times y_2+ \cdots + x_n \times y_n,两个 vector 中的元素可以任意更改位置。

思路:

v1v_1v2v_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;
}

证明:

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

假设存在另一种配对方式,使得标量积比 v1v_1 升序,v2v_2 降序的配对方式更小。

v1v_1 按升序排序 x1x2xnx_1 \le x_2 \le \cdots \le x_nv2v_2 降序排序 y1y2yny_1 \ge y_2 \ge \cdots y_n,这样的标量积为 S1=x1×y1+x2×y2++xn×ynS_1 = x_1 \times y_1 + x_2 \times y_2 + \cdots + x_n \times y_n

假设存在另一种配对方式,存在两个位置 iijjxix_iyjy_j 配对,xjx_jyiy_i 配对,且这种配对的标量积 S2<S1S_2 < S_1,则需要满足 xi×yi+xj×yj>xi×yj+xj×yix_i \times y_i + x_j \times y_j > x_i \times y_j + x_j \times y_i

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

  • xix_iyiy_i 配对,xjx_jyjy_j 配对,和为 xi×yi+xj×yjx_i \times y_i + x_j \times y_j
  • xix_iyjy_j 配对,xjx_jyiy_i 配对,和为 xi×yj+xj×yix_i \times y_j + x_j \times y_i

我们计算差值,以此比较大小:

作差法

因此,不存在比 v1v_1 升序,v2v_2 降序的配对方式更小的标量积。

故代码正确。