Name: Title:

 Name:
ONLINE COMPILERS
LIBRARY
MANUAL PAGES & DOCS
CONTACT

User Submitted Source Code!

Description:
solution.java
Language: JAVA
Code:
package candies;

import java.util.Arrays;

/**
* Alice is a teacher of kindergarten. She wants to give some candies to the
* children in her class. All the children sit in a line and each of them has a
* rating score according to his or her usual performance. Alice wants to give
* at least 1 candy for each children. Because children are somehow jealousy.
* Alice must give her candies according to their ratings subjects to for any
* adjacent 2 children if one's rating is higher than the other he/she must get
* more candies than the other. Alice wants to save money so she wants to give
* as few as candies in total.
*
*
* Input
*
* The first line of the input is an integre N, the number of children in
* Alice's class. Each of the following N lines contains an integer indicates
* the rating of each child.
*
* Ouput
*
* On the only line of the output print an integer describing the minimum number
* of candies Alice must give.
*
* Sample Input
*
* 3 1 2 2
*
* Sample Ouput
*
* 4
*
* Explanation
*
* The number of candies Alice must give are 1,2 and 1.
*
* Constraints:
*
* N and the rating of each children is no larger than 10^5.
*
*/
public class Solution {

private int[] rating;

private int[] candiesArray;

private boolean[] minArray;

private int totalCandies;

public static void main(String[] ars) throws Exception {
String line = br.readLine();
int N = Integer.parseInt(line);
int[] rating = new int[N];
for (int i = 0; i < N; i++) {
}

Solution candies = new Solution(rating);
candies.solve();
candies.output();
}

private void solve() {
for (int i = 0; i < rating.length; i++) {
if (i == 0) {
if (rating[i] < rating[i + 1]) {
minArray[i] = true;
}
} else if (i == rating.length - 1) {
if (rating[i] < rating[i - 1]) {
minArray[i] = true;
}
} else {
if (rating[i] < rating[i - 1] && rating[i] < rating[i + 1]) {
minArray[i] = true;
}
}
}

Arrays.fill(candiesArray, 1);

for (int i = 0; i < rating.length; i++) {
if (minArray[i]) {
for (int j = i - 1; j >= 0; j--) {
if (minArray[j])
break;
if (j == 0) {
if (rating[j] > rating[j + 1]) {
candiesArray[j] = candiesArray[j + 1] + 1;
}
} else {
if (rating[j] > rating[j - 1]
&& rating[j] > rating[j + 1]) {
candiesArray[j] = Math.max(candiesArray[j - 1],
candiesArray[j + 1]) + 1;
} else if (rating[j] > rating[j - 1]) {
candiesArray[j] = candiesArray[j - 1] + 1;
} else if (rating[j] > rating[j + 1]) {
candiesArray[j] = candiesArray[j + 1] + 1;
}
}
}
for (int k = i + 1; k < rating.length; k++) {
if (minArray[k])
break;
if (k == rating.length - 1) {
if (rating[k] > rating[k - 1]) {
candiesArray[k] = candiesArray[k - 1] + 1;
}
} else {
if (rating[k] > rating[k + 1]
|| rating[k] > rating[k - 1]) {
candiesArray[k] = Math.max(candiesArray[k - 1],
candiesArray[k + 1]) + 1;
} else if (rating[k] > rating[k + 1]) {
candiesArray[k] = candiesArray[k + 1] + 1;
} else if (rating[k] > rating[k - 1]) {
candiesArray[k] = candiesArray[i - 1] + 1;
}
}
}
}
}
}

private void output() {
for (int i = 0; i < rating.length; i++) {
totalCandies += candiesArray[i];
}
System.out.println(totalCandies);
}

public Solution(int[] rating) {
this.rating = rating;
candiesArray = new int[rating.length];
minArray = new boolean[rating.length];
}
}