題目

注意到題目中給出的具體例子中,只需要將兩個向量的分量分別升序和降序排列后再求點積就可以得到最小值,

為了嚴謹起見,下面給出該方法數(shù)學依據(jù)(排序不等式)的證明:

數(shù)學歸納法:

代碼

#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);
????}
?}?