[Logo] Форум DL
  [DL]  На главную страницу 
Индекс форума ->Олимпиадное программирование ->USACO Analyses
Автор Сообщение
Михаил Долинский

Темы: 1392
Сообщений: 33725

Мой профиль
(Analysis by Nick Wu)
In this problem, we have some notes about how Bessie's, Elsie's, and Mildred's milk outputs change over time. We wish to keep track of the number of days that the cows with the highest milk outputs change.

To compute this information, we need to maintain the milk outputs for each cow for each day when there is a change. At the beginning, we know that each cow outputs exactly 7 gallons of milk. We can go over the notes and figure out if any cow has a differing milk output. After doing so, we can directly determine which cows produced the most milk, and change if there were any changes.

Due to the small number of notes and days, it is not necessary to order the notes by day beforehand.

import java.io.*;
import java.util.*;
public class measurement {
	public static void main(String[] args) throws IOException {
		// initialize file I/O
		BufferedReader br = new BufferedReader(new FileReader("measurement.in"));
		PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("measurement.out")));
		// read in all of the notes
		int n = Integer.parseInt(br.readLine());
		int[] day = new int[n];
		String[] cow = new String[n];
		int[] change = new int[n];
		for(int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			day[i] = Integer.parseInt(st.nextToken());
			cow[i] = st.nextToken();
			change[i] = Integer.parseInt(st.nextToken());
		// the milk variables track the amount of milk that each cows was last known to produce
		int bessieMilk = 7, elsieMilk = 7, mildredMilk = 7;
		// the on variables are true if that cow produced the highest amount of milk on the previous day
		boolean bessieOn = true, elsieOn = true, mildredOn = true;
		int dayAdjust = 0;
		for(int currDay = 1; currDay <= 100; currDay++) {
			// look through the notes to see if there were any changes on this day
			for(int i = 0; i < n; i++) {
				if(day[i] == currDay) {
					if(cow[i].equals("Bessie")) {
						bessieMilk += change[i];
					if(cow[i].equals("Elsie")) {
						elsieMilk += change[i];
					if(cow[i].equals("Mildred")) {
						mildredMilk += change[i];
			// compute the highest milk total and see which cows produced the most milk 
			int highestMilk = Math.max(bessieMilk, Math.max(elsieMilk, mildredMilk));
			boolean bessieOnNext = bessieMilk == highestMilk;
			boolean elsieOnNext = elsieMilk == highestMilk;
			boolean mildredOnNext = mildredMilk == highestMilk;
			if(bessieOn != bessieOnNext || elsieOn != elsieOnNext || mildredOn != mildredOnNext) {
			bessieOn = bessieOnNext;
			elsieOn = elsieOnNext;
			mildredOn = mildredOnNext;

		// print the answer


Индекс форума ->Олимпиадное программирование ->USACO Analyses