My (perhaps over complicated) approach to solve the fourth problem was as follows. To order N meals : * let s be the sum of all the values of b[i] (1 <= i <= N)
* one meal k must be served as the first meal , that would decrease s by b[k]
then increase s by a[k] , hence it's optimal to choose k that minimizes a[k] - b[k]
* s <--- s + a[k] - b[k]
Then , to choose the best N — 1 meals , we either have to : Remove meal m != k which maximizes b[m] ( s <--- s - b[m] )
, or Remove meal k , and replace it with meal j which minimizes a[j] - b[j] ( s <--- s + a[j] - b[j])
We repeat the process N — 1 times to find the required answers for k = 1 through N
I only managed to implement it using 2 STL sets , which seems to exceed the memory limit of 32 MB (My solution passes 3 / 5 of official testcases scoring 72 / 120 , and returns SIGABRT on the remaining two)
I'd appreciate it a lot if someone expalins the intended approaches of this problem , or suggest some improvements (if any) to implement the above method
#include <cstdio>
#include <set>
using namespace std;
const int MAXN = 500001;
int N;
int a[MAXN];
int b[MAXN];
long long res[MAXN];
long long bsum;
int a_idx;
set < pair < int , int > > ordered_by_b;
set < pair < int , int > > ordered_by_diff;
set < pair < int , int > >::iterator it1;
set < pair < int , int > >::iterator it2;
pair < int , int > p1;
pair < int , int > p2;
int main(){
scanf("%d" , &N);
if(N > 100000)
goto FAIL;
for(int n = 1 ; n <= N ; n++){
scanf("%d %d" , &a[n] , &b[n]);
bsum += b[n];
ordered_by_b.insert(make_pair(-b[n] , n));
ordered_by_diff.insert(make_pair(a[n] - b[n] , n));
}
it1 = ordered_by_diff.begin();
p1 = *it1;
res[N] = bsum + p1.first;
a_idx = p1.second;
long long CASE_I , CASE_II;
for(int n = N - 1 ; n >= 1 ; n--){
it1 = ordered_by_b.begin();
p1 = *it1;
if(p1 == make_pair(-b[a_idx] , a_idx))
it1++;
p1 = *it1;
CASE_I = res[n + 1] + p1.first;
it2 = ordered_by_diff.begin();
it2++;
p2 = *it2;
CASE_II= res[n + 1] - a[a_idx] + p2.first;
if(CASE_I < CASE_II){
res[n] = CASE_I;
ordered_by_b.erase(p1);
ordered_by_diff.erase(make_pair(a[p1.second] - b[p1.second] , p1.second));
}
else {
res[n] = CASE_II;
ordered_by_b.erase(make_pair(-b[a_idx] , a_idx));
ordered_by_diff.erase(make_pair(a[a_idx] - b[a_idx] , a_idx));
a_idx = p2.second;
}
}
FAIL:
for(int n = 1 ; n <= N ; n++)
printf("%lld\n" , res[n]);
return 0;
}
2 sets are too big for this problem, I think.
How about just using a heap? We just have to get the minimum, or the maximum value.
Take a look at my reasonably simple solution for that task: link
Thanks a lot ! This is a very elegant and efficient solution.