Problem Info
Milk Measurement
http://www.usaco.org/index.php?page=viewproblem2&cpid=763
My Work
//Milk Measurement
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
struct Log{ //structure to store each measurement FJ makes
ll date, id, change;
};
bool comp(Log a, Log b) { //comparator function to sort the measurements based on date
return a.date < b.date;
}
int main()
{
ll n, g; //n, g
cin >> n >> g; //read in n, g
Log log[n];
for (int i = 0; i < n; i++) { //read in the measurements
cin >> log[i].date >> log[i].id >> log[i].change;
}
sort(log, log + n, comp); //sort the measurements by date
map <ll, set<ll>> milk_production; //key is milk, value is the set of all the ids of cows that produce key amount of milk
map <ll, ll> cow; //key is cow id, value is how much milk the cow produces
ll ans = 0; //answer
set <ll> leaderboard; //set that contains the cow(s) that produce the maximum amount of milk
for (int i = 0; i < n; i++) { //go through the sorted measurement
if (cow.find(log[i].id) == cow.end()) { //if the current measurement's cow id hasn't been seen in the map, add it to both maps.
cow[log[i].id] = log[i].change; //The cow produces log[i].change milk
milk_production[log[i].change].insert(log[i].id); //add the cow's id to the appropriate set in the first map
} else {
milk_production[cow[log[i].id]].erase(log[i].id); //remove the cow from it's previous set
cow[log[i].id] += log[i].change; //update the amount of milk it produces.
milk_production[cow[log[i].id]].insert(log[i].id); //add the cow to the new set.
}
set <ll> temp = milk_production[milk_production.rbegin()->first]; //set of cows with the maximum milk production value
if (temp != leaderboard) { //if the leaderboard is different from the current, increase the answer by 1 and update the leaderboard
ans++;
leaderboard = temp;
}
}
cout << ans << endl; //print the answer
}
Add explanation of code here
My solution approach:
First sort FJ’s measurements by date. Then keep 2 maps. The map named milk_production will have it’s key First sort FJ’s measurements by date. Then keep 2 maps. The map named milk_production will have its key equal to an amount of milk while its value will be the set of all cow ids that produce that much milk. The second map named cow will have its key equal to a cow id and its value will equal the amount of milk that cow produces. Keep a set named leaderboard that will store the current cows producing the maximum amount of milk. Then iterate through the sorted measurements. Update the current cow’s milk production and where it belongs in the first map. Now since maps are sorted by keys, the last key of the first map will give access to the set of cows that have been producing the most milk. Check to see if this set is equal to our leaderboard. If no, increase the answer by 1 and update the leaderboard. Keep doing this for the other measurements.