一个递增,一个递减。
#include <iostream> using namespace std; int cmp1(const void *a, const void *b) { int *p1 = (int *)a; int *p2 = (int *)b; return *p1 - *p2; } int cmp2(const void *a, const void *b) { int *p1 = (int *)a; int *p2 = (int *)b; return *p2 - *p1; } int main() { int t; cin >> t; for (int z = 0; z < t; z++) { int n; cin >> n; int a[1000], b[1000]; for (auto i = 0; i < n; i++) cin >> a[i]; for (auto i = 0; i < n; i++) cin >> b[i]; qsort(a, n, sizeof(int), cmp1); qsort(b, n, sizeof(int), cmp2); int sum = 0; for (auto i = 0; i < n; i++) sum += a[i] * b[i]; cout << "case #" << z << ":" << endl; cout << sum << endl; } return 0; }
using namespace std; bool cmp(int a,int b) { return a>b; } int main() { int t,i;cin>>t; for(i=0;i<t;i++){ int n;cin>>n; int *disc1=new int[n]; int *disc2=new int[n]; int j,k; for(j=0;j<n;j++) cin>>disc1[j]; for(j=0;j<n;j++) cin>>disc2[j]; sort(disc1,disc1+n); sort(disc2,disc2+n,cmp); int sum=0; for(j=0;j<n;j++) sum+=(disc1[j]*disc2[j]); cout<<"case #"<<i<<":"<<endl; cout<<sum<<endl; } }
the same as 2183 RT
两个向量都可以任意排,那么不妨固定其中一个变量 $a$。
两向量的内积可以想象为一个柱状图的面积。$a$ 各维度的值看作各个条形的宽度,$b$ 各维度的值看作各个条形的高度。现在,条形的宽度已经确定了,其总和也是确定的。我们只要把最宽的条与最大的高度相结合,就可以得到最大的面积。
所以,一个向量升序,一个向量降序,这就可以得到最大的积。
int main() { u32 t; cin >> t; array<i16, 1000> a; array<i16, 1000> b; for (u32 i = 0; i < t; ++i) { u32 n; cin >> n; for (u32 i = 0; i < n; ++i) cin >> a[i]; for (u32 i = 0; i < n; ++i) cin >> b[i]; sort(begin(a), begin(a) + n); sort(begin(b), begin(b) + n, greater<i16>()); cout << "case #" << i << ":\n" << inner_product(begin(a), begin(a) + n, begin(b), (i64)0) << '\n'; } }
排序不等式
可以用multiset 一个从begin() 一个从rbegin 比较方便
一个递增,一个递减。
include
the same as 2183
RT
最小向量点积题解
两个向量都可以任意排,那么不妨固定其中一个变量 $a$。
两向量的内积可以想象为一个柱状图的面积。$a$ 各维度的值看作各个条形的宽度,$b$ 各维度的值看作各个条形的高度。现在,条形的宽度已经确定了,其总和也是确定的。我们只要把最宽的条与最大的高度相结合,就可以得到最大的面积。
所以,一个向量升序,一个向量降序,这就可以得到最大的积。
排序不等式
可以用multiset 一个从begin() 一个从rbegin 比较方便