c++ - Running an infinite loop because of next_permute -
i trying solve problem input 2 vectors of different lengths , add scalar product. minimun scalar product problem https://code.google.com/codejam/contest/32016/dashboard#s=p0 . i'm apparently hopelessly running infinite loop.probably because of permutation.but don't understand why .
#include "stdafx.h"; #include <algorithm> #include <fstream> using namespace std; //output stuff int cases[100]; int casesol[100]; int ncase; void output() { (int = 1; <= ncase; i++) { printf("case #%d: %d\n", i, casesol[i]); } } //output stuff end int product; int v1[100]; int v2[100]; int minimum; int main() { // read in number of cases freopen("file.in", "r", stdin); freopen("file.out", "w", stdout); scanf("%d", &ncase); // read in misc problem constants (int = 1; <= ncase; ++i) { int vector_size; scanf("%d", &vector_size); // read in data //v1= new int [vector_size]; //v2=new int [vector_size]; (int j = 0; j < vector_size; ++j){ scanf("%d", &v1[j]); } (int j = 0; j < vector_size; ++j){ scanf("%d", &v2[j]); } // problem solving logic here do{ (int j = 0; j < vector_size; ++j){ product += v1[j] * v2[j]; } if (product<minimum) minimum = product; } while (next_permutation(v2 + 0, v2 + (vector_size - 1))); casesol[i] = minimum; } output(); return 0; }
the comment @nathanoliver made correct. think problem here in design. there easier solution problem looking at; minimum scalar vector max of 1 vector multiplied times min of other vector. consider code below:
const int size = 3; std::vector<int> v1 {1, 3, -5}; std::vector<int> v2 {-2, 4, 1}; std::sort(v1.begin(), v1.end()); std::sort(v2.begin(), v2.end()); int product = 0; (int = 0; < size; i++) { product += v1[i] * v2[size-1-i]; }
this first example page linked (hard coded instead of reading file). result correct, -25
.
Comments
Post a Comment