3003. 最小向量点积

Mr.wu_

一个递增,一个递减。

Andrew-Malcom

include

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;
        }
}
aiden
#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;
}
Deuchie

最小向量点积题解

两个向量都可以任意排,那么不妨固定其中一个变量 $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';
    }
}
gao_hf

排序不等式

10175101174

可以用multiset 一个从begin() 一个从rbegin 比较方便

51151201048

the same as 2183
RT

你当前正在回复 博客/题目
存在问题!