Analysis: Goldilocks and the N Cows, by Brian Dean
The process of solving this problem is described in the video above; the final code is shown below.
One small subtlety not discussed in the video above: if there is a tie between two elements -- one from the A array and the other from the B array -- it is important to process the one from the A array first (as we do in our code, since we check if A[i] <= B[j]). This ensures that we get the highest possible milk output at each temperature we consider, by first processing all the cows that become comfortable (entries in the A array), after which we process cows that become too hot (entries in the B array).
The total running time of this solution is O(N log N). The initial sorts run in O(N log N) time, then the ensuing scan through A and B takes only O(N) time.
#include <iostream> #include <fstream> #include <algorithm> #define MAX_N 20000 using namespace std; int N, X, Y, Z; int A[MAX_N+1], B[MAX_N+1]; int main(void) { ifstream fin("milktemp.in"); fin >> N >> X >> Y >> Z; for (int i=0; i<N; i++) fin >> A[i] >> B[i]; fin.close(); sort(A, A+N); sort(B, B+N); A[N] = 1000000001; B[N] = 1000000001; // scan through A and B simultaneously int i=0, j=0; int current_milk = N*X; int answer = N*X; while (i<N || j<N) { // look at A[i] and B[j]. if (A[i] <= B[j]) { // next event comes from A array current_milk += Y-X; i++; } else { // next event comes from B array current_milk += Z-Y; j++; } if (current_milk > answer) answer = current_milk; } ofstream fout("milktemp.out"); fout << answer << "\n"; fout.close(); return 0; }