首页 > 试题广场 >

N个孩子站成一排，给每个人设定一个权重（已知）。按照如下的规

[问答题]
N个孩子站成一排，给每个人设定一个权重（已知）。按照如下的规则分配糖果： (1)每个孩子至少分得一颗糖果 （2）权重较高的孩子，会比他的邻居获得更多的糖果。
问：总共最少需要多少颗糖果？请分析算法思路，以及算法的时间，空间复杂度是多少。
添加回答
牛客989465号头像 牛客989465号 
/*
N个孩子站成一排，给每个人设定一个权重（已知）。按照如下的规则分配糖果： (1)每个孩子至少分得一颗糖果 （2）权重较高的孩子，会比他的邻居获得更多的糖果。
问：总共最少需要多少颗糖果？请分析算法思路，以及算法的时间，空间复杂度是多少。
*/

#include <stdio.h>

void handout(int* child, int nCount, int* Candy, int* pTotalCandy);

int main()
{
    int nTotalCandy = 0;
    int childWeight[] = {1, 8, 3, 2, 2, 6, 4, 8};
    int candy[sizeof(childWeight) / sizeof(childWeight[0])] = {0};
    handout(childWeight, sizeof(childWeight) / sizeof(childWeight[0]), candy, &nTotalCandy);

    printf("Total:%d\n", nTotalCandy);
    for (int i = 0; i < sizeof(childWeight) / sizeof(childWeight[0]); i++)
    {
        printf("%d ", candy[i]);
    }
    printf("\n");
    return 0;    
}

void handout(int* childWeight, int nCount, int* Candy, int* pTotalCandy)
{
    int nLastCandy = 0;
    int nLastWeight = -1;
    int nTotalCandy = 0;
    for (int i = 0; i < nCount; i++)
    {
        //大于 糖果 + 1
        if (childWeight[i] > nLastWeight)
        {
            Candy[i] = ++nLastCandy;
            nLastWeight = childWeight[i];
            nTotalCandy += Candy[i];
        }
        //等于 糖果不变
        else if (childWeight[i] == nLastWeight)
        {
            Candy[i] = nLastCandy;
            nLastWeight = childWeight[i];
            nTotalCandy += Candy[i];
        }
        //小于 糖果 -1
        else if (childWeight[i] < nLastWeight)
        {
            Candy[i] = --nLastCandy;
            nLastWeight = childWeight[i];    
            nTotalCandy += Candy[i];
            //如果前一个糖果是1,则之前的每人再发一个
            if (nLastCandy == 0)
            {
                for (int j = 0; j <= i; j++)
                {
                    ++Candy[j];
                }
                nLastCandy++;
                nTotalCandy += i + 1;
            }
        }
    }
    *pTotalCandy = nTotalCandy;
}

发表于 2015-05-06 16:27:33 回复(3)
编号2015头像 编号2015
leetcode上的原题，先每人发一颗糖。第一遍从前往后扫描，满足相邻两个小孩后面的权重大于前面的权重的情况，后面的小孩在前面的小孩的糖果数的基础上加一个。第二遍从后往前扫描，满足条件与第一遍扫描一样。这样两遍扫描下来就可以保证权重高的孩子比相邻权重低的孩子的糖果多。时间复杂度是O(n)，空间复杂度是O(n)。 
int candy(vector<int> &ratings) {
        int i,j,sum = 0,min = ratings[0],n = ratings.size();
        int dp[n+1]={0};
        if (n<2)return 1;
        for (i = 0;i<n;i++)
            dp[i] = 1;
        
        for (i = 0;i<n;i++)
        {
            if (i<n-1&&ratings[i+1]>ratings[i])
                dp[i+1]=dp[i]+1;
        }
        for (i = n-1;i>=0;i--)
        {
            if (i>0&&ratings[i-1]>ratings[i]&&dp[i-1]<dp[i]+1)
                dp[i-1]=dp[i]+1;
            sum += dp[i];
        }
        return sum;
  }
编辑于 2015-10-27 16:41:34 回复(2)
Pandora头像 Pandora
所以其实题目的意思是不能排序的，因为给你排好序赋好权了o(╯□╰)o
发表于 2015-10-28 14:34:10 回复(0)
Aileng头像 Aileng
N不等于0，最少是N，最大是(1+N)N/2
发表于 2015-05-13 00:18:41 回复(0)
牛客874387号头像 牛客874387号
(n+1)*n/2
发表于 2015-05-06 23:58:21 回复(0)
AndyJee头像 AndyJee
class Solution {
public:
    int candy(vector<int>& ratings) {
        int n=ratings.size();
        int sum=0;
        
        vector<int> nums(n,1);
        vector<int> for_nums(n,1);
        vector<int> back_nums(n,1);
        
        for(int i=1;i<n;i++){
            if(ratings[i]>ratings[i-1])
                for_nums[i]=for_nums[i-1]+1;
        }
        
        for(int i=n-2;i>=0;i--){
            if(ratings[i]>ratings[i+1])
                back_nums[i]=back_nums[i+1]+1;
        }
        
        for(int i=0;i<n;i++){
            nums[i]=max(for_nums[i],back_nums[i]);
            sum+=nums[i];
        }
        
        return sum;
    }
};
发表于 2015-05-06 20:24:41 回复(0)
pretend头像 pretend
相当于一个等差数列，当然也可以用高斯定理，因为至少为1， 所以可以将第一个人分的设置为1，(1+n)*n/2，时间复杂度为1， 空间复杂度也为1
发表于 2015-05-06 17:48:50 回复(0)
不是惟有你头像 不是惟有你
如果排列顺序确定，那么就先给每个孩子发一颗糖，然后比较排在第二的孩子和排第一的孩子的权重，给权重大的孩子多一颗糖，然后从第二个孩子开始到倒数第二个孩子，依次比较该孩子与其下一个孩子的权重大小，如果权重较大的孩子的糖果数已经大于权重小的则继续，否则给权重大的孩子多一颗糖然后继续。
若是排列顺序不确定，则排序之后按从小到大的方式，则相邻较大的比较小的多一颗糖。

发表于 2015-05-06 17:03:13 回复(0)
牛客571930号头像 牛客571930号
可以先用冒泡排序根据权重从高到低排序,然后前面每个人币下一个人多一个糖果,所以需要n+(n-1)个糖果

发表于 2015-05-06 11:27:15 回复(0)
牛客665520号头像 牛客665520号
n个权重不同的孩子随机排列，进行分配
1、每个孩子分配一个；B[i]表示第i个孩子的糖果数
2、假设前面i-1个已分配好，现在分配第i个孩子，
   如果i权重较大，B[i]增加到比B[i-1]糖果多1，
   如果i权重较小，且B[i-1]等于B[i]，B[i-1]加1，然后i减1再进行循环
3、最后统计B[i]之和。
allocate(A,n){//数组A[i]是第i个孩子的权重i=1,...n
   array B[n];//糖果数
   count=0;
   for(i=1;i<=n;i++){
       B[i]=1;
   }
   for(i=2;i<=n;i++){
       if(A[i]==A[i-1])
             B[i] += B[i]-B[i-1];
       elseif(A[i]>A[i-1] && B[i]<=B[i-1]){
            B[i] += B[i]-B[i-1]+1;
       }
       elseif(A[i]<A[i-1] && B[i-1]<=B[i]){
            B[i-1]++;
            if(i>2)i--;
       }
   }
   for(i=1;i<=n;i++){
      count +=B[i];
   }
   return count;
}
空间复杂度O(n),最坏情况下，时间复杂度O(n^2),最好情况下，时间复杂度O(n).

发表于 2015-05-06 10:37:33 回复(0)
被眼前所蒙蔽头像 被眼前所蒙蔽
先：每个人发一个糖果
然后：从左往右或者从右往左，从第二个孩子开始发一个糖果，然后跳过第三个，给第四个发一个糖果，按照这个方法依次发完
从上得知：
    最少需要，当n为偶数时：n+n/2  
    当n为奇数时：n/2取整舍去余数 ：n+n/2
编辑于 2015-05-06 00:25:21 回复(0)
喜洋洋头像 喜洋洋
找出权重序列中的所有极小值，极小值对应的孩子分得1颗，每个极小值向两侧延伸，依次增加1颗，直至遇到极大值，极大值需计算2次
算法的时间、空间复杂度均为o(n)
发表于 2015-03-18 20:48:50 回复(1)
牛客192615号头像 牛客192615号
一个低权重，一个高权重，再一个低，一个高。。。。。。。如果N为单数且N！=1，需要的最少糖果为
（3N-1）/2颗，若N=1，则最少要1颗，弱N为偶数，则需要3N/2颗
发表于 2015-03-18 09:57:54 回复(0)
叫我小丑就好头像 叫我小丑就好
是3/2N个糖果吗 以为权重的不同而糖果的数量的不同如果是按顺序的从小到大或者从大到小的话那么最小权重就比最大权重少很多糖果所以要间隔排序这样的话就可以了吧应该
发表于 2015-03-17 15:13:00 回复(0)
提交观点

问题信息

编程基础 复杂度
来自：4399游戏2015校...
上传者：小牧魔法袋
难度：
14条回答 21560浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号