首页 > 试题广场 >

派分糖果

[编程题]派分糖果
  • 热度指数：2549 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

有N个孩子站成一排，每个孩子有一个分值。给这些孩子派发糖果，需要满足如下需求：

1、每个孩子至少分到一个糖果

2、分值更高的孩子比他相邻位的孩子获得更多的糖果

求至少需要分发多少糖果？


输入描述:
0,1,0


输出描述:
4
示例1

输入

5,4,1,1

输出

7
算法知识视频讲解
添加回答
pein531头像 pein531 
score = list(map(int, input().split(',')))
candy = [1]*len(score)
# 往左看调整糖果数
for i in range(1, len(score)):
    if candy[i] <= candy[i - 1] and score[i] > score[i - 1]:
        candy[i] = candy[i - 1] + 1
# 往右看调整糖果数
for i in range(len(score) - 2, 0, -1):
    if candy[i] <= candy[i + 1] and score[i] > score[i + 1]:
        candy[i] = candy[i + 1] + 1
print(sum(candy))

发表于 2020-11-26 16:22:08 回复(0)
Java
lmz9509头像 lmz9509 
/*
左右两次遍历，当 分数较高时，要为他加上糖果
类似于小米的厨师奖金分配题
*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(",");
        int[] score = new int[str.length];
        int[] sweet = new int[str.length];
        for(int i = 0;i<str.length;i++){
            score[i] = Integer.parseInt(str[i]);
            sweet[i]=1;
        }
        int sum = 0;
        //左遍历，分数高，糖果比你多；右边与左边比
        for(int i = 1;i<str.length;i++){
            if(score[i]>score[i-1]&& sweet[i]<=sweet[i-1])
                sweet[i] = sweet[i-1]+1;
        }
        
        //右遍历,分数高，糖果取最大的加1；左边与右边比
        for(int i = str.length -2;i>=0;i--){
            if(score[i]>score[i+1] && sweet[i]<=sweet[i+1])
                sweet[i] = Math.max(sweet[i],sweet[i+1])+1;
            sum+=sweet[i];
        }
        System.out.println(sum+sweet[str.length-1]);
    }
}

发表于 2020-05-17 11:41:07 回复(2)
JavaScript
萌萌萌哒头像 萌萌萌哒
JavaScript(Node) 😎题目:蘑菇街🍄-反派糖果  
const readline = require('readline')
const rl = readline.createInterface({
    input: process.stdin,
    ouput: process.stdout
})
let inArr = []
rl.on('line',line=>{
    if(!line) return
    inArr.push(line.trim())
    if(inArr.length === 1){
        let arr = inArr[0].split(',').map(e=>+e)
        let res = new Array(arr.length).fill(1)
        let len = arr.length
        let cnt = 0
        for(let i = 1 ; i < len ; i++){
            if(arr[i] > arr[i-1]){
                res[i] = res[i-1] + 1;
            }
        }
        for(let i = len -1 ; i > 0 ; i--){
            if(arr[i-1] > arr[i] && res[i-1] <= res[i]){
                res[i-1] = res[i] + 1;
            }
        }
        for(var i=0;i<len;i++){
             cnt += res[i];
        }
        // console.log(res)
        console.log(cnt)

    }
})
发表于 2020-02-26 23:27:34 回复(0)
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, x, s = 0;
    vector<int> a;
    while(cin>>x){
        a.push_back(x);
        if(cin.get()=='\n')
            break;
    }
    n = a.size();
    vector<int> b(n,1);
    for(int i=1;i<n;i++)
        if(a[i]>a[i-1])
            b[i] = b[i-1] + 1;
    for(int i=n-1;i>0;i--)
        if(a[i]<a[i-1] && b[i]>=b[i-1])
            b[i-1] = b[i] + 1;
    s = 0;
    for(int i=0;i<n;i++)
        s += b[i];
    cout<<s<<endl;     
    return 0;
}

发表于 2019-08-08 08:33:49 回复(0)
Polestar_a头像 Polestar_a 
score = list(map(int, input().split(',')))
res = [1]*len(score)
for i in range(1,len(score)):
    if score[i]>score[i-1]:
        res[i]=res[i-1]+1
for i in range(len(score)-2, -1,-1):
    if score[i]>score[i+1]:
        res[i] = max(res[i], res[i+1]+1)
print(sum(res))

发表于 2019-07-13 11:07:00 回复(0)
无心2019头像 无心2019 
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,sum=0;
    vector<int>num;
    while(cin>>n)
    {
        num.push_back(n);
        if(cin.get()=='\n')
            break;
    }
    vector<int>res(num.size(),1);
    for(int i=1;i<num.size();i++)
        if(num[i]>num[i-1])
            res[i]=res[i-1]+1;
    for(int i=num.size()-1;i>0;i--)
        if(num[i]<num[i-1]&&res[i]>=res[i-1])
            res[i-1]=res[i]+1;
    for(int i=0;i<num.size();i++)
        sum+=res[i];
    cout<<sum<<endl;
    return 0;
}

发表于 2019-07-06 22:32:05 回复(0)
会飞的小蜗牛头像 会飞的小蜗牛

import java.util.Arrays;
import java.util.Scanner;

public class Test2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入一串数字");
        int sum = 0;
        String line = sc.nextLine();
        String[] sArr = line.split(",");

        int[] arr = new int[sArr.length];

        for (int i = 0; i < arr.length; i++) {
            arr[i] = Integer.parseInt(sArr[i]); // 将数字字符串转换成数字
        }

        int[] member = new int[arr.length];
        Arrays.fill(member, 1);

        for (int j = 1; j < arr.length; j++) {
            if (arr[j] > arr[j - 1]) {
                member[j] = Math.max(member[j], member[j - 1] + 1);
            }
        }

        for (int j = arr.length - 2; j >= 0; j--) {
            if (arr[j] > arr[j + 1])
                member[j] = Math.max(member[j], member[j + 1] + 1);
        }

        for (int i = 0; i < member.length; i++) {
            sum = sum + member[i];
        }

        System.out.println(sum);
    }

}

编辑于 2019-04-01 10:08:50 回复(2)
Python
ElonB头像 ElonB 
""""
从左至右，看自己左侧的分数，若比自己小，在他的基础上加一
从右至左，看自己右侧的分数，若比自己小，max(自己，右侧+1)
"""

if __name__ == "__main__":
    a = list(map(int, input().strip().split(',')))
    n = len(a)
    ans = [1] * n
    for i in range(1, n):
        if a[i] > a[i - 1]:
            ans[i] = ans[i - 1] + 1
    for i in range(n - 2, -1, -1):
        if a[i] > a[i + 1]:
            ans[i] = max(ans[i], ans[i + 1] + 1)
    print(sum(ans))

发表于 2019-07-16 12:23:27 回复(1)
请给我个offer,谢谢头像 请给我个offer,谢谢 
class Solution {
    public int candy(int[] ratings) {
        int[] left = new int[ratings.length];
        int[] right = new int[ratings.length];
        Arrays.fill(left, 1);
        Arrays.fill(right, 1);
        for(int i = 1; i < ratings.length; i++)
            if(ratings[i] > ratings[i - 1]) left[i] = left[i - 1] + 1;
        int count = left[ratings.length - 1];
        for(int i = ratings.length - 2; i >= 0; i--) {
            if(ratings[i] > ratings[i + 1]) right[i] = right[i + 1] + 1;
            count += Math.max(left[i], right[i]);
        }
        return count;
    }
}

引用力扣大佬的答案：
规则定义： 设学生 AA 和学生 BB 左右相邻，AA 在 BB 左边；
左规则： 当 ratings_B>ratings_Aratings 
B
    
 >ratings 
A
    
 时，BB 的糖比 AA 的糖数量多。
右规则： 当 ratings_A>ratings_Bratings 
A
    
 >ratings 
B
    
 时，AA 的糖比 BB 的糖数量多。
相邻的学生中，评分高的学生必须获得更多的糖果 等价于 所有学生满足左规则且满足右规则。

算法流程：

先从左至右遍历学生成绩 ratings，按照以下规则给糖，并记录在 left 中：

先给所有学生 11 颗糖；
若 ratings_i>ratings_{i-1}ratings 
i
    
 >ratings 
i−1
    
 ，则第 ii 名学生糖比第 i - 1i−1 名学生多 11 个。
若 ratings_i<=ratings_{i-1}ratings 
i
    
 <=ratings 
i−1
    
 ，则第 ii 名学生糖数量不变。（交由从右向左遍历时处理。）
经过此规则分配后，可以保证所有学生糖数量 满足左规则 。
同理，在此规则下从右至左遍历学生成绩并记录在 right 中，可以保证所有学生糖数量 满足右规则 。

最终，取以上 22 轮遍历 left 和 right 对应学生糖果数的 最大值 ，这样则 同时满足左规则和右规则 ，即得到每个同学的最少糖果数量。

复杂度分析：

时间复杂度 O(N)O(N) ： 遍历两遍数组即可得到结果；
空间复杂度 O(N)O(N) ： 需要借用left，right的线性额外空间。

作者：jyd
链接：https://leetcode-cn.com/problems/candy/solution/candy-cong-zuo-zhi-you-cong-you-zhi-zuo-qu-zui-da-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

发表于 2021-03-19 11:06:38 回复(0)
louis_ncu头像 louis_ncu 
//双向遍历法
//同 2019网易校招，厨艺大赛奖金
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <limits.h>

using namespace std;

void DeliverSugar() {
    int num;
    char ch;
    vector<int> vec;
    while (cin >> num) {
        vec.push_back(num);
        cin >> ch;
    }
    int len = vec.size();
    vector<int> dp(len, 1);
    //从左向右
    for (int i = 1; i < len; i++) {
        if (vec[i] > vec[i - 1]) {
            dp[i] = dp[i-1] + 1;
        }
    }
    //从右向左
    for (int i = len - 1; i > 0; i--) {
        if (vec[i - 1] > vec[i]) {
            dp[i - 1] = max(dp[i - 1], dp[i] + 1);
        }
    }
    int res = 0;
    for (int i = 0; i < len; i++) {
        res += dp[i];
    }
    cout << res << endl;
}

int main(){
    DeliverSugar();
    return 0;
}
编辑于 2020-07-05 13:06:09 回复(2)
AnnaSophia_Robb头像 AnnaSophia_Robb 
#include <bits/stdc++.h>
using namespace std;

int main(){
    int num;
    vector<int> arr;
    while(cin >> num){
        arr.push_back(num);
        if(cin.get()=='\n')
            break;
    }
    int n = arr.size();
    vector<int> left(n, 1), right(n, 1);
    int pre = arr[0], add = 1;
    for(int i=1; i<n; i++){
        if(arr[i] > arr[i-1]){
            left[i] += add;
            add++;
        }else add = 1;
    }
    pre = arr[n-1]; add = 1;
    num = 0;
    for(int i=n-2; i>=0; i--){
        if(arr[i] > arr[i+1]){
            right[i] += add;
            add++;
        }else add = 1;
        num += max(left[i], right[i]);
    }
    cout << num+left[n-1];
    return 0;
}

发表于 2020-02-18 00:11:36 回复(0)
1辰头像 1辰 
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] str = in.nextLine().split(",");
        int[] candy = new int[str.length];
        for(int i = 0; i < str.length; i ++)
            candy[i] = Integer.valueOf(str[i]);
        int res = 1;
        int pre = 1;
        int dis = 0;
        for(int i = 1; i < candy.length; i ++) {
            if(candy[i] >= candy[i - 1]) {
                if(dis > 0) {
                    res += dis * (dis + 1) / 2;
                    if(dis >= pre)
                        res += dis - pre + 1;
                    dis = 0;
                    pre = 1;
                }
                pre = candy[i] == candy[i - 1] ? 1 : pre + 1;
                res += pre;
            }
            else dis += 1;
        }
        if(dis > 0) {
            res += dis * (dis + 1) / 2;
            if(pre <= dis)
                res += dis - pre + 1;
        }
        System.out.println(res);
    }
} //贪心，补糖是重点。实际上是等差数列求和的应用，但是要注意给降序之前的小朋友补糖。一次遍历。
发表于 2019-11-06 16:22:29 回复(0)
C/C++
昔遥暮云头像 昔遥暮云 
#include <bits/stdc++.h>
using namespace std;
int main(){
    vector<int> arr;
    while(1){
        int t;
        cin>>t;
        arr.push_back(t);
        if(cin.get()=='\n')
            break;
    }
    vector<int> dp(arr.size(),1);
    dp[0]=1;
    for(int i=1;i<arr.size();i++){
        if(arr[i]>arr[i-1])
            dp[i]=dp[i-1]+1;
    }
    for(int i=arr.size()-2;i>=0;i--){
        if(arr[i]>arr[i+1])
            dp[i]=max(dp[i],dp[i+1]+1);
    }
    int sum=0;
    for(int i=0;i<arr.size();i++)
        sum+=dp[i];
    cout<<sum;
    return 0;
}

发表于 2019-10-21 11:35:30 回复(0)
Python
汤普森30头像 汤普森30 
nums = list(map(int, input().split(',')))
candy = [1 for _ in range(len(nums))]
for i in range(1, len(nums)):
    if nums[i] >nums[i-1]:
        candy[i] = candy[i-1] +1
for i in range(len(nums)-2, -1, -1):
    if nums[i] > nums[i+1]:
        candy[i] = max(candy[i], candy[i+1]+1)
print(sum(candy))

发表于 2019-09-01 15:29:26 回复(0)
小蝌蚪666头像 小蝌蚪666 
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
int main(void){
    vector<int> score;
    vector<int> candy;
    int x;
    while(cin>>x){
        score.push_back(x);
        candy.push_back(1);
        if(cin.get() == '\n')
            break;
    }
    for(int i = 1; i < score.size(); ++i)
        if(score[i] > score[i-1] && candy[i] <= candy[i-1])
            candy[i] = candy[i-1]+1;
    for(int j = score.size()-1; j > 0; --j)
        if(score[j] < score[j-1] && candy[j] >= candy[j-1])
            candy[j-1] = candy[j]+1;
    cout<<accumulate(candy.begin(), candy.end(), 0)<<endl;
    return 0;
}
从左到右，从右到左两次遍历，遇到升序，糖果数目要比前面一个加1
发表于 2019-08-26 17:14:48 回复(0)
Sliencebear头像 Sliencebear 
import java.util.Arrays;
import java.util.Scanner;

/**
 * @Author: kunrong
 * @Date: 2019/8/16 16:27
 * @Description:
 **/
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str[] = sc.nextLine().split(",");
        int n = str.length;
        int a[] = new int[n];
        int l = 0;
        for (String i : str) {
            a[l++]= Integer.parseInt(i);
        }
        int dp[] = new int[n];
        Arrays.fill(dp,1);
        for (int i = 1; i < n; i++) {
            if (a[i]>a[i-1]&&dp[i]<=dp[i-1]){
                dp[i]= dp[i-1]+1;
            }
        }

        for (int i = n-2;i >= 0; i--) {
            if(a[i]>a[i+1]&&dp[i]<=dp[i+1]) {
                dp[i] = dp[i+1]+1;
            }
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            res+=dp[i];
        }
        System.out.println(res);
    }
}

发表于 2019-08-16 16:53:08 回复(0)
PopcornZQ头像 PopcornZQ 
#include<iostream>
#include<vector>
#include<string>
#include <numeric>
#include <algorithm>
using namespace std;
int main()
{
    vector<int>zq;//每人分一个
    string temp;
    cin >> temp;
    for (int i = 0; i < temp.size(); i = i + 2)
        zq.push_back(temp[i]-'0');
    vector<int>candy(zq.size(), 1);
    for (int i = 1; i < zq.size(); ++i)
        if (zq[i] > zq[i - 1])
            candy[i]= candy[i-1]+1;//全员向左看
    for (int i = zq.size() - 2; i >= 0; --i)
        if (zq[i] > zq[i + 1])
            candy[i] = max(candy[i],candy[i + 1] + 1);//全员向右看
    cout <<  accumulate(candy.begin(), candy.end(), 0) << endl;
    return 0;
}

编辑于 2019-08-12 10:18:41 回复(0)
哈啰内推2021头像 哈啰内推2021
input1=input().split(',')
list1=list(map(int,input1))
num=[]
for i in range(len(list1)):
    num.append(0)
for i in range(len(list1)):
    if i==0:
        num[i]=1
    if i>0:
        if list1[i]>list1[i-1]:
            num[i]=num[i-1]+1
        if list1[i]<=list1[i-1]:
            num[i]=1
num1=[]
for i in range(len(list1)):
    num1.append(0)
for i in range(len(list1)-1,-1,-1):
    if i==len(list1)-1:
        num1[i]=1
    if i<len(list1)-1:
        if list1[i]>list1[i+1]:
            num1[i]=num1[i+1]+1
        if list1[i]<=list1[i+1]:
            num1[i]=1
sum1=0
for i in zip(num,num1):
    sum1=sum1+max(i)
print(sum1)
发表于 2019-04-07 18:33:21 回复(0)
芯★淡茹水头像 芯★淡茹水 
function DispatchApple() {
    var arr = Array.prototype.slice.call(arguments, 0).sort();
    var data = 1;
    var total = 0;
    for (var i=0;i<arr.length;i++) {
        if (i > 0 && arr[i] > arr[i-1]) data++;
        total += data;
    }
    return total;
}
alert(DispatchApple(0,1,0));    // 4 
alert(DispatchApple(5,4,1,1));  // 7

发表于 2019-03-30 14:43:06 回复(0)
提交观点

问题信息

C++工程师 贪心 系统工程师 数组 算法工程师 图 2019 大数据开发工程师 蘑菇街 排序 Java工程师
上传者：小小
难度：
19条回答 6546浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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