大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE稳定放心使用
有两个向量 v1=(x1,x2,...,xn) 和 v2=(y1,y2,...,yn) ,允许任意交换 v1 和 v2 各自的分量的顺序，计算 v1 和 v2 的内积 x1y1+x2y2+...+xnyn 的最小值
样例：
输入：
n=3
v1=(1,3,−5)
v2=(−2,4,1)
输出:
-25
( 令 v1=(−5,1,3) ， v2=(4,1,−2) )
首先我第一感觉就是，要保证最小，
1.如果在有正有负的情况下，那么有最大的正数乘以最小的负数，
2.如果都是正数，用最大的正数乘以最小的正数，
3.如果都是负数，用最大的负数数乘以最小的负数，
其实以上的3个条件就是两个向量分别按照升序和降序排列，得到的内积最小
按照上面的方法，不断的从 v1 和 v2 取出配对的量，最后得出的结果可能是最优的结果。
举个样例试一试
v1=(x1,x2) , v2=(y1,y2)
如果 v1 已经是按照升序排列，即 x1≤x2 ,比较 x1×y1+x2×y2 和 x1×y2+x2×y1 的大小
(x1×y1+x2×y2)−(x1×y2+x2×y1)
=(x1(y1−y2)+x2(y2−y1))
=(x1−x2)(y1−y2)
可以看出，如果 y1<y2 ,即 x1×y1+x2×y2>x1×y2+x2×y1
意味着，我们可以通过交换 y1和y2 的位置得到一个更小的向量内积值
延伸到 n>2
我们也同样把 V1 按照升序排列，对于 v2 如果存在 i<j,并且yi<yj 我们可以通过交换 yi和yj 的位置，得到一个更小的例子
x1y1+...+xiyi+...+xjyj+...+xnyn>x1y1+...+xiyj+...+xjyi+...+xnyn
#include <iostream>
#include <algorithm>
using namespace std;
int compare(int a,int b)
{
return a>b;
}
int main()
{
int n,i;
cout<<"input n: ";
cin>>n;
cout<<endl;
cout<<"input v1 :"<<endl;
int *v1=new int[n];
int *v2=new int[n];
for(i=0;i<n;i++)
{
cin>>v1[i];
}
cout<<"input v2 :"<<endl;
for(i=0;i<n;i++)
{
cin>>v2[i];
}
//v1 升序
sort(v1,v1+n);
//v2 降序
sort(v2,v2+n,compare);
int min=0;
for(i=0;i<n;i++){
min+=v1[i]*v2[i];
}
cout<<"minimum is :"<<min<<endl;
delete [] v1;
delete [] v2;
return 0;
}
input n: 3
input v1 :
1 3 -5
input v1 :
-2 4 1 minimum is :-25发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/189960.html原文链接：https://javaforall.net
