有两个向量v1=(x1,x2,x3,,,xn)和v2=( y1,y2,,,,yn),允许任意交换v1和v2各自的分量的顺序。请计算v1和v2的内积x1y1+,,,,+xnyn的最小值。
限制条件
Small
1<=n<=8,-1000<Xi,Yi<=1000
Large
100<=n<=800
-100000<=Xi,Yi<100000
样例1:
输入:
n=3
V1=(1,3,-5)
v2=(-2,4,1)
输出:-25
分析:首先把数组排序,用升序的数组乘以另一个降序的数组即可,注意要把他们的乘积定义为longlong 类型的,防止溢出
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{int n;int a[1000];int b[1000];while(cin>>n){for(int i=0;i<n;i++)cin>>a[i];for(int j=0;j<n;j++)cin>>b[j];sort(a,a+n);sort(b,b+n);long long ans=0;for(int i=0;i<n;i++)ans+=a[i]*b[n-1-i];printf("%lld\n",ans);}return 0;
}