首页 > 代码库 > 编程挑战高校俱乐部分配糖果答案

编程挑战高校俱乐部分配糖果答案

2024-07-22 20:23:22   219人阅读

题目详情
有n个小朋友站成一排（编号从0到n-1)，每个小朋友有一个rating值，存放在ratings数组中。老师需要给他们分配糖果，每个小朋友至少需要一颗糖果，对于任意相邻的两个小朋友i和i+1，rating值大的必须比rating值小的分配的糖果多（rating相同的没必要分配一样多的糖果）。

请计算最少需要多少颗糖果，才能完成上述分配。


输入格式：
多组数据，每组数据第一行是一个正整数n。
接下来n行,每行有1个正整数，表示每个小朋友的rating值。所有整数都不超过100000。
输出格式：
每组数据一行，包括一个正整数，表示做少需要的糖果数。

答题说明
输入样例
3
1
2
2
输出样例：

4

挑战成功，代码如下：

import java.util.Scanner;

public class Children {
    
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        
        int n = 0;
        int sweetCount = 0;
        while (cin.hasNext()) {
            sweetCount = 0;
            n = cin.nextInt();
            int[] ratings = new int[n];
            for (int i = 0; i < n; i++) {
                ratings[i] = cin.nextInt();
            }
            
            int[] sweets = new int[n];
            sweets[n - 1] = 1;
            for (int i = n - 1; i > 0; i--) {
                int j = i;
                if (ratings[j] < ratings[j - 1]) {
                    sweets[j - 1] = sweets[j] + 1;
                }
                else if (ratings[j] == ratings[j - 1]) {
                    sweets[j - 1] = 1;
                }
                else {
                    if (sweets[j] == 1) {
                        for (int k = j; k < n; k++) {
                            sweets[k]++;
                            if (k == n - 1 || ratings[k] >= ratings[k + 1]
                                || (ratings[k] < ratings[k + 1] && sweets[k] < sweets[k + 1]))
                                break;
                        }
                    }
                    sweets[j - 1] = 1;
                }
            }
            
            for (int i : sweets) {
                sweetCount += i;
            }
            System.out.println(sweetCount);
            
        }
        cin.close();
    }
}


编程挑战高校俱乐部分配糖果答案


联系
我们