幼儿园老师想给她班上的孩子分饼干。所有的孩子都坐在一条线上,每个孩子都根据在课堂上的表现得到评分。老师必须给每个孩子至少1个饼干。如果两个孩子坐在一起,那么评分较高的孩子必须得到更多的饼干(孩子必须左右都比较)。输出老师购买的饼干总数的最小值。例如,假设她的学生的评分为[3,6,3,5,6,2]。她给学生饼干的数量如下:[1,2,1,2,3,1]。她必须购买至少10个饼干。
幼儿园老师想给她班上的孩子分饼干。所有的孩子都坐在一条线上,每个孩子都根据在课堂上的表现得到评分。老师必须给每个孩子至少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行为数组元素(每行一个)
可分配最小值
6 3 6 3 5 6 2
10
孩子数量为6(第一个数),所以饼干数位 1+2+1+2+3+1=10
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); } }
#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; }
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))