c语言发橙子问题求解

Question

请问哪里错了，在洛谷平台上提交通过不了，题目是这样的，每年的 1024 程序员节日，黑马程序员都会举办大型的庆祝活动。今年的程序员节也不例外，每个班级的同学都发了橙子。

班级里有
n 名同学从前到后排成一排，且已经得知了这些同学的成绩，其中第 a
i 名同学的成绩是 a i
​班主任想根据同学们上个阶段的考试成绩来评定发橙子的数量。为了激励成绩优秀同学，发橙子时需要满足如下要求：

相邻同学中成绩好的同学的橙子必须更多。若相邻的同学成绩一样，则它们分到的数量必须平等。
每个同学至少分配一个橙子
由于预算有限，班主任希望在符合要求的情况下发出尽可能少的橙子。请问，至少需要准备多少橙子呢？

输入格式
第一行是一个整数 n，表示学生数量。
接下来一行有 n 个整数，第 i 个整数 a i，表示第 i 个同学的成绩。
输出格式
输出答案，也就是需要最少准备多少个橙子。
以下是代码

#include<stdio.h>
#include<stdlib.h>
int main()
{
    int n=0;
    scanf("%d",&n);
    int* b=(int*)malloc(sizeof(int)*n);
    int* a=(int*)malloc(sizeof(int)*n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
        b[i]=1;                             //1 2 1 1 2
    }                                       //1 2 1 1 2
    for(int j=0;j<n-1;j++)
    {
        if(a[j]==a[j+1])
        {
            b[j+1]=b[j];
        }
        else if(a[j]>a[j+1])
        {
            if(b[j]==b[j+1]) b[j]+=1;  
            else continue;       
        }
        else if(a[j]<a[j+1])
        {
            b[j+1]=1+b[j];
        }
    }
    int count=0;
    for(int i=0;i<n;i++)
    {
        count+=b[i];
    }
    printf("%d",count);
    system("pause");
    return 0;
}

Answer 1

这是一个经典的贪心算法问题。根据题目描述，我们可以按照以下步骤来解决这个问题：

创建一个数组 oranges[] 用来存储每个同学应该获得的橙子数量，初始化所有元素为1，表示每个同学至少分配一个橙子。
从左到右遍历学生的成绩，检查每对相邻学生的成绩，如果后面的学生成绩比前面的好，则后面的学生应该获得前面的学生橙子数量加1。
累加所有同学应该获得的橙子数量，得到最少需要准备的橙子数。
下面是一个用 C 语言编写的实现：

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);

    int scores[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &scores[i]);
    }

    int oranges[n];
    for (int i = 0; i < n; i++) {
        oranges[i] = 1;
    }

    // 从左到右遍历学生的成绩，更新橙子数量
    for (int i = 1; i < n; i++) {
        if (scores[i] > scores[i - 1]) {
            oranges[i] = oranges[i - 1] + 1;
        }
    }

    // 累加所有学生应该获得的橙子数量
    int totalOranges = 0;
    for (int i = 0; i < n; i++) {
        totalOranges += oranges[i];
    }

    printf("%d\n", totalOranges);

    return 0;
}

这段代码首先读取学生数量和每个学生的成绩，然后根据贪心算法的原则计算出最少需要准备多少个橙子