Google Code Marmelade minimale Skalar Produkt funktioniert nicht auf meine Auswahl Sortierung (C++)

Question

Ich war im vergangenen Jahr Code Marmelade Probleme geübt und minimale skalare Produkt gefunden.
Problem Link: https://code.google.com/codejam/contest/32016/dashboard#s=p0
Ich weiß, wie sein Algorithmus funktioniert. Wir sortieren beide Arrays v1 und v2 und multiplizieren dann v1 [j] * v2 [n-1-j]. Der Algorithmus funktioniert gut, wenn ich C++ Standard sort() -Funktion verwenden. Aber wenn ich meine eigene Sortierfunktion (Auswahlsortierung) verwende, erhalte ich unterschiedliche Ausgaben.
Weiter beobachtete ich die korrekte Ausgabedatei Ich bemerkte, dass, wenn alle Eingabe Zahlen und positive meine Ausgabe korrekt ist. Für negative Zahlen ist es jedoch falsch. Hier ist der Code meiner Sortierfunktion:

`void sorted(long long int *a,int n) 
{ 
long long int temp; 
int minIndex; 
for(int i=0;i<n;i++) 
{ 
    minIndex=i; 
    for(int j=i+1;j<n;j++) 
    { 
     if(a[i]>a[j]) 
      minIndex=j; 
    } 
    if(minIndex!=i) 
    { 
     temp=a[minIndex]; 
     a[minIndex]=a[i]; 
     a[i]=temp; 
    } 
} 
} 
` 

Beachten Sie, dass für dieses Problem, das wir long long int weil Eingangszahlen überschreiten int Grenzen verwenden. Das ist meine Hauptaufgabe ist:

#include <iostream> 
#include<fstream> 
using namespace std; 
void sorted(long long int *a,int n); 
int main() 
{ 
    ifstream inp("input.in"); 
    int T; 
    inp>>T; 
    int n[T]; 
    long long int *x[T], *y[T]; 
    for(int i=0;i<T;i++) 
    { 
     inp>>n[i]; 
     x[i]=new long long int[n[i]]; 
     y[i]=new long long int[n[i]]; 
     for(int j=0;j<n[i];j++) 
      inp>>x[i][j]; 
     for(int j=0;j<n[i];j++) 
      inp>>y[i][j]; 
    } 
    long long int minProduct[T]; 
    ofstream out("output.txt"); 

    for(int i=0;i<T;i++) 
    { 
     minProduct[i]=0; 
     sorted(x[i],n[i]); 
     sorted(y[i],n[i]); 
     for(int j=0;j<n[i];j++) 
      minProduct[i]=minProduct[i]+(y[i][n[i]-1-j]*x[i][j]); 
     out<<"Case #"<<i+1<<": "<<minProduct[i]<<endl; 
    } 
    return 0; 
} 

wenn ich

ersetzen

sorted(x[i],n[i]); 
sorted(y[i],n[i]); 

mit

sort(x[i],x[i]+n[i]); 
sort(y[i],y[i]+n[i]); 

einschließlich Algorithmus Header-Datei, ist meine Ausgabe korrekt. Was ist der Fehler in meinem Sortieralgorithmus?

Answer 1

In der Schleife, wo Sie den minimalen Index finden, müssen Sie den aktuellen Eintrag im Index j mit dem Element an der aktuellen Index des Minimums Artikel vergleichen:

minIndex = i; 

    for (int j = i + 1; j < n; j++) { 
     if (a[minIndex] > a[j]) 
      minIndex = j; 
    } 

Sie mit dem Element bei Index immer vergleichen i und daher nicht für Updates auf minIndex.