Given two arrays, A and B, of equal size n, the task is to find the minimum value of A[0] * B[0] + A[1] * B[1] +…+ A[n-1] * B[n-1], where shuffling of elements of arrays A and B is allowed.
Examples:
Input : A[] = {3, 1, 1} and B[] = {6, 5, 4}.
Output : 23 Minimum value of S = 1*6 + 1*5 + 3*4 = 23.
Input : A[] = { 6, 1, 9, 5, 4 } and B[] = { 3, 4, 8, 2, 4 }
Output : 80. Minimum value of S = 1*8 + 4*4 + 5*4 + 6*3 + 9*2 = 80.
Input:
The first line of input contains an integer denoting the no of test cases. Then T test cases follow. Each test case contains three lines. The first line of input contains an integer N denoting the size of the arrays. In the second line are N space separated values of the array A[], and in the last line are N space separated values of the array B[].
Output:
For each test case in a new line print the required result.
Constraints:
1<=T<=100
1<=N<=50
1<=A[]<=20
Example:
Input:
2
3
3 1 1
6 5 4
5
6 1 9 5 4
3 4 8 2 4
Output:
23
80
Your Code
#include<iostream>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int i,j;
int a[100],b[100];
int n;
cin>>n;
for(i=0; i<n; i++)
{
cin>>a[i];
}
for(i=0; i<n; i++)
{
cin>>b[i];
}
for(i=0; i<n-1; i++)
{ int c=i;
int d=i;
for(j=i+1; j<n; j++)
{
if(a[c]>=a[j])
{
c=j;
}
if(b[d]>=b[j])
{
d=j;
}
}
if(c!=i)
{
int temp=a[i];
a[i]=a[c];
a[c]=temp;
}
if(d!=i)
{
int temp1=b[i];
b[i]=b[d];
b[d]=temp1;
}
}
/* for(i=0; i<n; i++)
{
// cout<<a[i]<<" ";
cout<<b[i]<<" ";
}*/
int sum=0;
for(i=0;i<n; i++)
{
sum=sum+a[i]*b[n-1-i];
//cout<<a[i]*b[n-1-i]<<endl;
}
cout<<sum<<endl;
}
}