Largest sum issue
| mbozzi wrote: |
|---|
| nth_element might be better than partial_sort |
Yes, you are right!
I hadn't realised at the time that it effects a partition, not just places the nth element itself.
It's a seemingly under-used (at least by me) part of <algorithm>.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int sumBestTwo( vector<int> &V )
{
nth_element( V.begin(), V.begin() + 1, V.end(), greater<int>() );
return V[0] + V[1];
}
int main()
{
vector< vector<int> > tests = { { 122, 117, 28, 9, 1, 27, 6, 111, 322 }, { 5, 9, 7, 11 } };
for ( auto &V : tests ) cout << sumBestTwo( V ) << '\n';
}
|
Last edited on
Topic archived. No new replies allowed.