USACO 2017 February Contest, Bronze Problem 2. Why Did the Cow Cross the Road II

原题下载

USACO2017-FEB-B2

答案

import java.io.*;
import java.util.*;
public class circlecross {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new FileReader("circlecross.in"));
PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("circlecross.out")));

// read in the crossings
String crosses = br.readLine();
// convert the string to an array of integers for simplicity
int[] crossArray = new int[crosses.length()];
for(int i = 0; i < crosses.length(); i++) {
crossArray[i] = crosses.charAt(i) - 'A';
}

int numPairs = 0;

// track the first and last occurrence of each numbers
for(int i = 0; i < 26; i++) {
int first = getFirstAppearance(crossArray, i);
int last = getLastAppearance(crossArray, i);
// count the number of single appearances within the range
numPairs += getNumberOfSingles(crossArray, i, first, last);
}

pw.println(numPairs);

pw.close();
}

/**
* Given an array of integers and some value, return the first index of the
* value. Return -1 if the value does not appear in the array.
* @param crossArray The array to inspect.
* @param desiredValue The value to look for in the given array.
* @return The first index where desiredValue appears in crossArray, or -1 if it doesn't.
*/
public static int getFirstAppearance(int[] crossArray, int desiredValue) {
for(int i = 0; i < crossArray.length; i++) {
if(crossArray[i] == desiredValue) {
return i;
}
}
return -1;
}

/**
* Given an array of integers and some value, return the last index of the
* value. Return -1 if the value does not appear in the array.
* @param crossArray The array to inspect.
* @param desiredValue The value to look for in the given array.
* @return The last index where desiredValue appears in crossArray, or -1 if it doesn't.
*/
public static int getLastAppearance(int[] crossArray, int desiredValue) {
for(int i = crossArray.length-1; i >= 0; i--) {
if(crossArray[i] == desiredValue) {
return i;
}
}
return -1;
}

/**
* Given an array of integers, a range of indices, and a lower bound, compute how many values
* greater than the lower bound appear exactly once inside the range. The range of indices
* is exclusive on the left and right indices.
* @param crossArray The array to inspect.
* @param greaterThan The lower bound of values we are interested in.
* @param leftIndex The left index (exclusive) of the range we are querying.
* @param rightIndex The right index (exclusive) of the range we are querying.
* @return
*/
public static int getNumberOfSingles(int[] crossArray, int greaterThan, int leftIndex, int rightIndex) {
int numSingles = 0;
// keep track of the number of times a given number has appeared
int[] appearances = new int[26];
// loop over the range and update how many times a given number has appeared
for(int i = leftIndex+1; i < rightIndex; i++) {
appearances[crossArray[i]]++;
}
// loop over each of the numbers from the lower bound (exclusive) and
// count how many have appeared exactly once
for(int i = greaterThan + 1; i < appearances.length; i++) {
if(appearances[i] == 1) {
numSingles++;
}
}
return numSingles;
}

}