USACO Silver 2017 December - Milk Measurement

Authors: Qi Wang, Kevin Sheng, Benjamin Qi

Edit This Page

Official Analysis (C++)

Solution with Sorted Map

Implementation

Time Complexity: O(Nlog⁡N)\mathcal{O}(N\log N)

C++

#include <algorithm>
#include <fstream>
#include <iostream>
#include <map>
#include <vector>


using std::cout;
using std::endl;
using std::vector;

Java

import java.io.*;
import java.util.*;


public class Measurement {
 	Code Snippet: Log Class (Click to expand)


	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("measurement");
		int n = io.nextInt();
		int g = io.nextInt();

Solution with Priority Queue

An alternative method to keep track of the maximum milk production is to use a priority queue instead of a sorted map. All the sorted maps from the solution code above can be left as is or interchanged with hashmaps.

Implementation

C++

#include <algorithm>
#include <cassert>
#include <fstream>
#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>


using std::endl;
using std::vector;

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum