Is this similar to knapsack problem, what sort of functions should I use?
There are N chocolates and several boxes. Each chocolate has its own calories. Each box can contain at most 2 chocolates and you don't want the total calories of each box to exceed .
Given the calories of each chocolate, please output the minimum required boxes to pack all chocolates.
Input Format
The first line has two integers N and C.
The second line has N integers: the calories of each chocolate.
similar in some ways but it is far less difficult due to the additional rules.
you have a starting point .. 1 box per piece.
every time you find a pair that works, you can reduce by 1 and remove that pair.
a simple sort of the data gives NlgN run time + a little more, and there may be a way to avoid the sort even. You do not have to check every combination for every pair.
eg after sorting:
2 3 7 9
try 9 and 2, no, so 9 goes by itself into a box, remove 9.
2 3 7
try 7 and 2, success,
3 remains, box it.
something like that where you take the lowest and highest each time, if its too big, you take the highest alone, if not take both, ...
Multiset is a little sluggish, but it shouldn't be enough to fail your code.
All that tells me is there must be a O(n) answer, and I don't see it right now.
But, does it actually work? On your test cases, not submitted?
#include <iostream>
#include <vector>
#include <algorithm>
usingnamespace std;
int main()
{
int N, C;
vector<int> lower, higher;
cin >> N >> C;
// int half = N / 2; // errorint half = C / 2;
for ( int k = 0; k < N; k++ )
{
int value;
cin >> value;
if ( value <= half ) lower .push_back( value );
else higher.push_back( value );
}
sort( lower .begin(), lower .end() );
sort( higher.begin(), higher.end() );
int boxes = higher.size();
if ( higher.size() > lower.size() ) higher.resize( lower.size() ); // Some boxes will be unpairable
int i = 0, j = higher.size() - 1;
for ( ; j >= 0; j-- ) // Pair off any higher[] that can
{
if ( lower[i] + higher[j] <= C ) i++;
}
// Fix what is left over
if ( i < lower.size() ) boxes += ( 1 + lower.size() - i ) / 2; // An even number of lower[] can be paired off
cout << boxes;
}
With your prev(A.end()) being O(N) for any sort of set I suspect your method is either O(N^{2}) or O(N^{2} logN) (sorry, struggling to work out which with the erase in as well).
#include <iostream>
#include <vector>
#include <algorithm>
usingnamespace std;
int main()
{
int N, C;
vector<int> lower, higher;
cin >> N >> C;
int half = C / 2;
for ( int k = 0; k < N; k++ )
{
int value;
cin >> value;
if ( value <= half ) lower .push_back( value );
else higher.push_back( value );
}
sort( lower .begin(), lower .end() );
sort( higher.begin(), higher.end() );
int boxes = higher.size();
if ( higher.size() > lower.size() ) higher.resize( lower.size() ); // Some boxes will be unpairable
int i = 0, j = higher.size() - 1;
for ( ; j >= 0; j-- ) // Pair off any higher[] that can
{
if ( lower[i] + higher[j] <= C ) i++;
}
// Fix what is left over
if ( i < lower.size() ) boxes += ( 1 + lower.size() - i ) / 2; // An even number of lower[] can be paired off
cout << boxes;
}