c++ - Google Code Jam 最小标量积

Question

我正在解决来自 Google Code Jam 的问题，但我无法解决问题:http://code.google.com/codejam/contest/32016/dashboard#s=p0 (最小标量积，问题 A 2008)

我使用的策略是:

1. 接受用户的v1和v2
2. 同时对 v1 和 v2 进行排序
3. 反转v2即降序排列v2
4. 将对应的v1[i] * v2[i]直接相乘，结果存入product
5. 汇总所有此类产品并打印答案

我做了一些研究，确实这似乎是唯一可能获得的排列。但是，我的代码没有产生正确的输出:

#include <stdio.h>
#include <algorithm>
#include <iostream>

using namespace std;
int main()
{

    int T;
    int cases;
    FILE *fin  = fopen ("A-small-practice.in", "r"); // open input file
    FILE *fout = fopen ("output.out", "w");

    fscanf(fin, "%d", &T);
    for(cases = 1; cases <= T; cases++)
    {
        int v1[1000], v2[1000];
        int i,j; int n;
        int product =0;
        fscanf(fin, "%d", &n);

        for(i=0; i < n; i++)
        {            
            fscanf(fin, "%d",&v1[i]);
            fscanf(fin, "%d", &v2[i]);            
        }

        sort(v1,v1+n);
        sort(v2,v2+n);
        reverse(v1, v1+n);

        int k;
        for(k = 0; k < n; k++)
        {                        
            product += v1[k] * v2[k];            
        }
        fprintf(fout, "Case #%d: %d\n", cases, product);
    }
    return 0;    
}

Answer 1

你应该使用long long。 这对我有用:

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
long long T,n,v1[1000],v2[1000];
cin >> T;
for (int t = 1; t <= T; t++) {
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> v1[i];
    for (int i = 0; i < n; i++)
        cin >> v2[i];
    sort(v1,v1+n);
    sort(v2,v2+n);
    long long p = 0;
    for (int i = 0; i < n; i++)
        p += v1[i]*v2[n-i-1];
    cout << "Case #" << t << ": " << p << endl;
}
return 0;
}