18图灵班作业4-编程

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

直觉判断这个可以用贪心解法，毕竟暴力枚举是不可能的，下面证明以下贪心策略（可能）正确：
将v1按从小到大排序，v2按从大到小排序，则有最终结果为

$$x_1y_1+x_2y_2+x_3y_3+\ldots+x_{n-1}y_{n-1}+x_ny_n$$

$$假设v1有\\ x_1<x_2<x_3<\ldots<x_{n-1}<x_n\\ v2有\\ y_1>y_2>y_3>\ldots>y_{n-1}>y_n\\ 取任意a,b值(a<b),调换y_a,y_b，则有\\ t1=x_1y_1+x_2y_2+\ldots+x_ay_a+\ldots+x_by_b+\ldots+x_{n-1}y_{n-1}+x_ny_n\\ t2=x_1y_1+x_2y_2+\ldots+x_ay_b+\ldots+x_by_a+\ldots+x_{n-1}y_{n-1}+x_ny_n\\ t1-t2=(x_ay_a+x_by_b)-(x_ay_b+x_by_a)=(x_a-x_b)(y_a-y_b)\\ 因为x_a<x_b,y_a>y_b,所以t1<t2$$

首先，我们可以把其中一个向量看成是不变的，例如v1是按从小到大排序的，改变v2的排列顺序，求两个向量内积的最小值。
由上面的证明知道，当以v2按从大到小排序为初态时，再调换v2中某两个元素的位置，内积会增大。
又因为可以通过继续两两调换v2中其他的任意两个元素从而产生v2的全排列，而根据上一行的结论，内积会变的更大，因此v2按从大到小排序，v1按从小到大排序时内积最小。

还有一点，进行第二次调换的时候v2不是已经不是标准序了吗？“再调换v2中某两个元素的位置，内积会增大”这个结论仍然成立的理由是：我们把v1、V2中未相乘的元素按原先顺序排列组成一个新的序列，则该序列仍然满足一开始的前提————“v1从小到大，v2从大到小”。

综上，v1从小到大,v2从大到小排序后的点积最小。当v2中任意两个元素调换顺序（逆序对？）的时候，点积会增大。

由此可知，调换任意两个元素的顺序都会使结果变大
我们可以接着把未被调换的元素看成新的数列，它们仍然是标准序，那么接着调换它们中的任意两个，结果又会接着变大，因此，以上结论成立

最后是代码

#include <algorithm>
#include <cstdio>
using namespace std;
bool LessComparer(int t1,int t2){
    return t1<t2;
}
bool GreatComparer(int t1,int t2){
    return t1>t2;
}
int main(){
    int n;
    scanf("%d",&n);
    int* vector1;
    int* vector2;
    vector1=(int*)malloc(sizeof(int)*n);
    vector2=(int*)malloc(sizeof(int)*n);
    sort(vector1,vector1+n,LessComparer);
    sort(vector2,vector2+n,GreatComparer);
    int ans=0;
    for(int i=0;i<n;i++){
        ans+=vector1[i]*vector2[i];
    }
    printf("%d\n",ans);
    return 0;
}