题目

注意到题目中给出的具体例子中,只需要将两个向量的分量分别升序和降序排列后再求点积就可以得到最小值,

为了严谨起见,下面给出该方法数学依据(排序不等式)的证明:

数学归纳法:

代码

#include<stdio.h>
#include<stdlib.h>

int cmp1(const void *a,const void *b) //从小到大 
{
    int *m=(int*)a;
    int *n=(int*)b;
    return *m-*n;
}

int cmp2(const void *a,const void *b) //从大到小 
{
    int *m=(int*)a;
    int *n=(int*)b;
    return *n-*m;
}

int main()
{
    int T;
    scanf("%d",&T);
    for(int i=0;i<T;i++)
    {
        int n;
        scanf("%d",&n);
        int vector1[n],vector2[n];
        for(int j=0;j<n;j++)
        {
            scanf("%d",&vector1[j]);
        }
        for(int j=0;j<n;j++)
        {
            scanf("%d",&vector2[j]);
        }
        qsort(vector1,n,sizeof(int),cmp1);
        qsort(vector2,n,sizeof(int),cmp2);
        long long count=0;
        for(int j=0;j<n;j++)
        {
            count+=vector1[j]*vector2[j];
        } 
        printf("case #%d:\n",i);
        printf("%lld\n",count);
    }
 }