Minimum Scalar Product HRBUST - 1754

本文主要是介绍Minimum Scalar Product HRBUST - 1754，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

You are given two vectors v1=(x1,x2,...,xn) and v2=(y1,y2,...,yn). The scalar product of these vectors is a single number, calculated as x1y1+x2y2+...+xnyn.

Suppose you are allowed to permute the coordinates of each vector as you wish. Choose two permutations such that the scalar product of your two new vectors is the smallest possible, and output that minimum scalar product.

Input

There are multiple test cases.

For each test case, the first line contains integer number n. The next two lines contain n integers each (1<=n<=800), giving the coordinates of v1 and v2 respectively.

 Process to the end of file.

Output

For each test case, output a line X, where X is the minimum scalar product of all permutations of the two given vectors.

Sample Input

3
1 3 -5
-2 4 1
5
1 2 3 4 5
1 0 1 0 1

Sample Output

-25
6

题意：

给你一个数字n，代表有n个数字，后面跟着n个数字，让你求出来sum=a[1]*b[1]+a[2]*b[2]+.......+a[n]*b[n];

其中，n个数字的数据你可以随意排序，求出来sum的最小值；

思路：

直接把数组按照由小到大的顺序进行排序，然后sum=a[ i ] * b[ n-i ]  (i=1,2,3,4,5),求出的sum就是最小值；

需要注意的是：数据范围（long long)；

代码如下：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;long long int a[1010],b[1010];int main()
{int n;while(~scanf("%d",&n)){for(int i=0; i<n; i++)scanf("%lld",&a[i]);for(int i=0; i<n; i++)scanf("%lld",&b[i]);sort(a,a+n);sort(b,b+n);long long int sum=0;for(int i=0; i<n; i++){sum+=a[i]*b[n-i-1];}printf("%lld\n",sum);}return 0;
}

 

这篇关于Minimum Scalar Product HRBUST - 1754的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---