程序员人生 网站导航

Minimum Scalar product

栏目:php教程时间:2015-05-26 07:33:58

有两个向量v1=(x1,x2,x3,,,xn)和v2=( y1,y2,,,,yn),允许任意交换v1和v2各自的份量的顺序。请计算v1和v2的内积x1y1+,,,,+xnyn的最小值。

限制条件

Small

1<=n<=8,⑴000<Xi,Yi<=1000

Large

100<=n<=800

⑴00000<=Xi,Yi<100000

样例1:

输入:

n=3

V1=(1,3,⑸)

v2=(⑵,4,1)

输出:⑵5

分析:首先把数组排序,用升序的数组乘以另外一个降序的数组便可,注意要把他们的乘积定义为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⑴-i]; printf("%lld ",ans); } return 0; }



------分隔线----------------------------
------分隔线----------------------------

最新技术推荐