首页 > 代码库 > Candy

Candy

2024-07-06 10:56:19   222人阅读

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

  • Each child must have at least one candy.
  • Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

class Solution {
public:
    int candy(vector<int> &ratings) 
    {
        int n=ratings.size();
        if(n<2) return n;
        
        int candys[n];
        for(int i=0;i<n;i++) candys[i]=0;
        
        int cnt=0;
        while(cnt<n)
        {
            for(int i=0;i<n;i++)
            if(candys[i]==0)
            {
                if((i==0 && (ratings[i+1]>=ratings[i]||candys[i+1]>0)) 
                || (i==n-1 && (ratings[i-1]>=ratings[i] || candys[i-1]>0)))
                {
                    if(i==0)
                    {
                        if(ratings[1]==ratings[0]) candys[0]=1;
                        else candys[0]=candys[1]+1;
                    }
                    else
                    {
                        if(ratings[n-1]==ratings[n-2]) candys[n-1]=1;
                        else candys[n-1]=candys[n-2]+1;
                    }
                    cnt++;
                    if(i>0 && candys[i-1]==0) i=i-2;
                    continue;
                }
                if(i>0 && i<n-1 && 
                (candys[i-1]>0 || ratings[i-1]>=ratings[i]) && (candys[i+1]>0  || ratings[i+1]>=ratings[i]))
                {
                    candys[i]=1;
                    if(ratings[i-1]<ratings[i]) candys[i]=candys[i-1]+1;
                    if(candys[i]<=candys[i+1] && ratings[i+1]<ratings[i])
                        candys[i]=candys[i+1]+1;
                    cnt++;
                    if(i>0 && candys[i-1]==0) i=i-2;
                    continue;
                }
            }
        }
        int sum=0;
        for(int i=0;i<n;i++) sum=sum+candys[i];
        return sum;
    }
};

 


联系
我们