首页 > 试题广场 >

分饼干

[编程题]分饼干
  • 热度指数:474 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

     幼儿园老师想给她班上的孩子分饼干。所有的孩子都坐在一条线上,每个孩子都根据在课堂上的表现得到评分。老师必须给每个孩子至少1个饼干。如果两个孩子坐在一起,那么评分较高的孩子必须得到更多的饼干(孩子必须左右都比较)。输出老师购买的饼干总数的最小值。例如,假设她的学生的评分为[3,6,3,5,6,2]。她给学生饼干的数量如下:[1,2,1,2,3,1]。她必须购买至少10个饼干。



输入描述:
假设学生评分为:[1,2,3],则输入应为:

3

1

2

3

第1行为数组元素大小,2至n+1行为数组元素(每行一个)


输出描述:
可分配最小值
示例1

输入

6
3
6
3
5
6
2

输出

10

说明

孩子数量为6(第一个数),所以饼干数位  1+2+1+2+3+1=10
示例2

输入

10
2
4
2
6
1
7
8
9
2
1

输出

19

说明

孩子数量为10,  所以饼干数为  1+2+1+2+1+2+3+4+2+1=19 (最后一个孩子获得一个饼干,但是他比前一个孩子评分小,所以前一个孩子饼干数加一)
贪心算法:先从左往右遍历,检查每个孩子的左边是否有低分多饼的情况,如果存在,则以最小限度超过他;再从右往左遍历,检查每个孩子的右边是都有低分多饼的情况,如果存在,同样以最小限度超过他,以此保证饼干总数最少。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] scores = new int[n];
        for(int i = 0; i < n; i++) scores[i] = Integer.parseInt(br.readLine());
        int[] cookie = new int[n];
        Arrays.fill(cookie, 1);
        for(int i = 1; i < n; i++)
            if(scores[i] > scores[i - 1] && cookie[i] <= cookie[i - 1]) cookie[i] = cookie[i - 1] + 1;
        for(int i = n - 2; i >= 0; i--)
            if(scores[i] > scores[i + 1] && cookie[i] <= cookie[i + 1]) cookie[i] = cookie[i + 1] + 1;
        int totalCookie = 0;
        for(int i = 0; i < n; i++) totalCookie += cookie[i];
        System.out.println(totalCookie);
    }
}

发表于 2021-07-20 12:22:43 回复(0)
用了一种我自己都不知道是什么的方法......
#include <iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    if(!n){
        cout<<0<<endl;
        return 0;
    }
    int*arr=new int[n];
    for(int i=0;i<n;++i)
        cin>>arr[i];
    int last=1,ind=0;
    long long sum=1;
    bool flag=0;
    for(int i=1;i<n;++i){
        if(arr[i]>arr[i-1]){
            if(flag){
                last=2;
                flag=0;
            }
            else
                last++;
            sum+=last;
            ind=i;
        }
        else if(arr[i]==arr[i-1]){
            ind=i;
            last=1;
            sum+=1;
        }
        else{
            flag=1;
            sum+=i-ind;
            if(last==1){
                sum+=1;
            }
            else
                --last;
        }
    }
    delete[]arr;
    cout<<sum<<endl;
    return 0;
}

发表于 2021-11-04 21:31:13 回复(0)
复杂度O(n)
**暴力版,正着来一遍,反着来一遍
n = int(input().strip())
num_list = []
for i in range(n):
    num_list.append(int(input().strip()))
if n == 0:
    print(0)
else:
    weight_list, new_weight_list = [1] * n, [1] * n
    temp_cnt = 1
    for i in range(1, n):
        if num_list[i - 1] < num_list[i]:
            temp_cnt += 1
        else:
            temp_cnt = 1
        weight_list[i] = temp_cnt
    temp_cnt = 1
    for i in range(n - 1, 0, -1):
        if num_list[i - 1] > num_list[i]:
            temp_cnt += 1
        else:
            temp_cnt = 1
        new_weight_list[i - 1] = temp_cnt
    for i in range(n):
        if new_weight_list[i] > weight_list[i]:
            weight_list[i] = new_weight_list[i]

print(sum(weight_list))


发表于 2021-06-19 18:33:12 回复(0)