2008 round1A :Minimum Scalar Product

GCJ

keyword

C++

概要

同じ長さの数列が2つ与えられる。適当に順序を入れ替えてできる内積の最小値を求める問題。
小さい値の寄与を大きくして、大きい値の寄与を小さくすればいいんだから降順と昇順にしたものの内積をとれば良さそう。本当か？取りあえず書く量は多くないので試してみる。サンプルは合った。smallもlargeのもちゃんと通った。

int main(){
    int t, n, i, loop;
    ll xs[1000], ys[1000];

    cin >> t;

    REPONE(loop, t){
        cin >> n;
        REP(i,n) scanf("%lld", xs+i);
        REP(i,n) scanf("%lld", ys+i);
        sort(xs, xs+n);
        sort(ys, ys+n);
        reverse(ys,ys+n);
        printf("Case #%d: %lld\n", loop, inner_product(xs, xs+n, ys, 0ll));
    }

    return 0;
}