Dining Cows

From Progteam

Revision as of 15:30, 22 April 2009 by Andrew.stone (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search


Checkmark.jpg This problem has been solved by Eric.



Dining Cows
Problem Number 3671
Sorter: Eric
Source: USACO 2008 February Bronze
Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=3671




Dining Cows is problem number 3671 on the Peking University ACM site.

Contents

Problem Information

Problem Name: Dining Cows
Problem Number on PKU: 3671
Synopsis: FJ's job as a farmer is to line up cows so that "1" cows are in front of "2" cows. What is the minimum number of cards he has to switch in order to line them up properly?

Solver Information

Solver: Eric Hong
Date: September 21, 2008

Trivia

This is NOT a sorting problem.

General Strategy

  1. Using Scanner, take the input.
  2. Populate the numbers into an array.
  3. Find the number of 1's in the array.
  4. Count every "2" as a swap, and find the minimum number of these keeping in mind we do not need to swap "1".


Solution

import java.util.*;

public class Main
{
	public static Scanner in;

	public static void main(String[] args)
	{
		in = new Scanner(System.in);
		doStuff();
	}

	public static void doStuff()
	{
		int numCase = in.nextInt();
		int[] cards = new int[numCase];
		
		for (int i = 0; i < numCase; i++)
			cards[i] = in.nextInt();
		
		solve(cards);
	}

	public static void solve(int[] cards)
	{
		int oneCount = 0;
		int size = cards.length;
		
		for (int i = 0; i < size; i++)
		{
			if (cards[i] == 1)
				oneCount++;
		}
		
		int min = oneCount;
		
		for (int i = 0; i < size; i++)
		{
			if (cards[i] == 1)
				oneCount--;
			else
				oneCount++;
			
			if (oneCount < min)
				min = oneCount;
		}
		
		System.out.println(min);
	}
}


Additional Remarks

Memory: 4980K
Time: 2235MS

This solution may not be as efficient as it can be.

Personal tools