Ask Question

Name:
Title:
Your Question:

Answer Question

Name:
Your Answer:
User Submitted Source Code!


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

import java.io.BufferedReader;
import java.io.InputStreamReader;
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 {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          String line = br.readLine();
          int N = Integer.parseInt(line);
          int[] rating = new int[N];
          for (int i = 0; i < N; i++) {
               rating[i] = Integer.parseInt(br.readLine());
          }

          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];
     }
}

Comments: