candy（动态规划）

题目描述

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?

题意：n 个小孩，每个小孩有一个评分。给小孩发糖。要求：

　　　　1)每个小孩至少一颗糖

　　　　2)评分高的小孩发的糖比他旁边两个小孩的多

因此最少需要多少糖果才够分？

解题思路：

　　遍历两边，首先每个人得一块糖，第一遍从左到右，若当前点比前一个点高就比前者多一块。

这样保证了在一个方向上满足了要求。第二遍从右往左，若左右两点，左侧高于右侧，但

左侧的糖果数不多于右侧，则左侧糖果数等于右侧糖果数+1，这就保证了另一个方向上满足要求。

　　最后将各个位置的糖果数累加起来就可以了。

代码实现：

class Solution {

public:

    int candy(vector<int> &ratings) {

        int n=ratings.size();

        //candy set

        vector<int>Candy(n,);

        //from left to right

        for(int i();i<n-;i++){

            if(ratings[i+]>ratings[i])

                Candy[i+]=Candy[i]+;

        }

        //from right to left

        for(int j=n-;j>;j--){

            if(ratings[j-]>ratings[j]&&Candy[j-]<=Candy[j])

                Candy[j-]=Candy[j]+;

        }

        //add all

        int sum();

        for(auto a:Candy)

            sum+=a;

        return sum;

    }

};

巴特西

candy（动态规划）

题目描述

解题思路：

代码实现：

最新文章

热门文章