一群孩子做游戏，现在请你根据游戏得分来发糖果，要求如下：
1. 每个孩子不管得分多少，起码分到一个糖果。
2. 任意两个相邻的孩子之间，得分较多的孩子必须拿多一些糖果。
3. 任意两个相邻的孩子之间的得分如果一样多，糖果数必须相同
给定一个数组arr代表得分数组，请返回最少需要多少糖果。
[编程题]分糖果问题进阶问题
从左往右按照题中规则调整一遍糖果数，然后从右往左再调整一遍糖果数即可
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());
String[] strArr = br.readLine().split(" ");
int[] scores = new int[n];
for(int i = 0; i < n; i++) scores[i] = Integer.parseInt(strArr[i]);
int[] candy = new int[n];
Arrays.fill(candy, 1);
// 从左往右
for(int i = 1; i < n; i++){
if(scores[i] > scores[i - 1] && candy[i] <= candy[i - 1]){
candy[i] = candy[i - 1] + 1; // 最小限度超过邻居
}else if(scores[i] == scores[i - 1]){
candy[i] = candy[i - 1];
}
}
// 从右往左
for(int i = n - 2; i >= 0; i--){
if(scores[i] > scores[i + 1] && candy[i] <= candy[i + 1]){
candy[i] = candy[i + 1] + 1;
}else if(scores[i] == scores[i + 1]){
candy[i] = candy[i + 1];
}
}
int total = 0;
for(int i = 0; i < n; i++) total += candy[i];
System.out.println(total);
}
}
发表于 2021-06-29 15:42:06
回复(0)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
int a[n], b[n], s=0;
for(int i=0;i<n;i++){
cin>>a[i];
b[i] = 1;
}
for(int i=1;i<n;i++){
if(a[i-1]<a[i])
b[i] = b[i-1] + 1;
else if(a[i-1]==a[i])
b[i] = b[i-1];
}
for(int i=n-2;i>=0;i--){
if(a[i]>a[i+1])
b[i] = max(b[i], b[i+1]+1);
else if(a[i]==a[i+1])
b[i] = b[i+1];
}
for(int i=0;i<n;i++)
s += b[i];
cout<<s<<endl;
return 0;
}
发表于 2020-03-22 00:41:31
回复(0)
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String count = sc.nextLine();
int n = Integer.parseInt(count);
int[] nums = new int[n];
int[] candy = new int[n];
String numStr = sc.nextLine();
String[] numArr = numStr.split(" ");
for (int i = 0; i < numArr.length; i++) {
nums[i] = Integer.parseInt(numArr[i]);
candy[i] = 1;
}
for (int i = 1; i < n; i++) {
if (nums[i] > nums[i - 1]) {
candy[i] = candy[i - 1] + 1;
} else if (nums[i] == nums[i - 1]) {
candy[i] = candy[i - 1];
}
}
for (int i = n - 1; i >= 1; i--) {
if (nums[i - 1] > nums[i] && candy[i - 1] <= candy[i]) {
candy[i - 1] = candy[i] + 1;
} else if (nums[i - 1] == nums[i]) {
candy[i - 1] = candy[i];
}
}
int sum = 0;
for (int i = 0; i < n; i++) {
sum += candy[i];
}
System.out.println(sum);
}
}
发表于 2020-06-20 14:52:29
回复(0)
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String array_len = in.nextLine();
// 获取数组长度
int[] score = new int[Integer.parseInt(array_len)];
String aString = in.nextLine();
String[] a = aString.split(" ");
// 获取分数数组
for (int i = 0; i < a.length; i++) {
score[i] = Integer.parseInt(a[i]);
}
System.out.println(cal_min_candy(score));
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String array_len = in.nextLine();
// 获取数组长度
int[] score = new int[Integer.parseInt(array_len)];
String aString = in.nextLine();
String[] a = aString.split(" ");
// 获取分数数组
for (int i = 0; i < a.length; i++) {
score[i] = Integer.parseInt(a[i]);
}
System.out.println(cal_min_candy(score));
}
public static int cal_min_candy(int[] a) {
int[] temp=new int[a.length];
Arrays.fill(temp, 1);
//右看一下，发现比自己小的就比小的多一个
for(int j=1;j<temp.length;j++) {
if(a[j]>a[j-1]) {
temp[j]=temp[j-1]+1;
}
else if(a[j]==a[j-1]) {
temp[j]=Math.max(temp[j], temp[j-1]);
}
}
//左看一下，发现比自己小且糖果比自己多的，就比小的多一个
for(int j=temp.length-2;j>=0;j--) {
if(a[j]>a[j+1]&&temp[j]<=temp[j+1]) {
temp[j]=temp[j+1]+1;
}
else if (a[j]==a[j+1]) {
temp[j]=Math.max(temp[j], temp[j+1]);
}
}
return sunArray(temp);
}
public static int sunArray(int[] a) {
int sum = 0;
for (int i = 0; i < a.length; i++) {
sum += a[i];
}
return sum;
}
}
int[] temp=new int[a.length];
Arrays.fill(temp, 1);
//右看一下，发现比自己小的就比小的多一个
for(int j=1;j<temp.length;j++) {
if(a[j]>a[j-1]) {
temp[j]=temp[j-1]+1;
}
else if(a[j]==a[j-1]) {
temp[j]=Math.max(temp[j], temp[j-1]);
}
}
//左看一下，发现比自己小且糖果比自己多的，就比小的多一个
for(int j=temp.length-2;j>=0;j--) {
if(a[j]>a[j+1]&&temp[j]<=temp[j+1]) {
temp[j]=temp[j+1]+1;
}
else if (a[j]==a[j+1]) {
temp[j]=Math.max(temp[j], temp[j+1]);
}
}
return sunArray(temp);
}
public static int sunArray(int[] a) {
int sum = 0;
for (int i = 0; i < a.length; i++) {
sum += a[i];
}
return sum;
}
}
发表于 2020-02-17 11:56:58
回复(0)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n; scanf("%d", &n);
vector<int> arr(n);
vector<int> left(n,1);
vector<int> right(n,1);
int temp = INT_MAX, add = 1;
for(int i=0; i<n; i++){
scanf("%d", &arr[i]);
if(arr[i] > temp){
left[i] += add;
add++;
}else if(arr[i] < temp){
add = 1;
}else{
left[i] = left[i-1];
}
temp = arr[i];
}
temp = arr[n-1];
add = 1;
int ans = left[n-1];
for(int i=n-2; i>=0; i--){
if(arr[i] > temp){
right[i] += add;
add++;
}else if(arr[i] < temp){
add = 1;
}else{
right[i] = right[i+1];
}
temp = arr[i];
ans += max(left[i], right[i]);
}
printf("%d", ans);
return 0;
}
发表于 2020-02-13 14:15:55
回复(0)
这个代码不知道是不是判断相同个数的语句出错了，没能通过import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { // 1.读入数据 Scanner in = new Scanner(System.in); //将第一行数字当做字符串处理，然后使用包装类型的方法将字符串转为int类型 //parseInt方法要求字符串必须由纯数字组成，否则有NumberFormatException异常 int n = Integer.parseInt(in.nextLine().trim()); String s = in.nextLine().trim(); //split按空格拆分字符串，注意返回值是字符串数组而非字符串 String elem[]=s.split(" "); int arr[]=new int[elem.length];//创建数组存储第二行输入数据 for(int i=0;i<arr.length;i++){ arr[i]=Integer.parseInt(elem[i]); //将字符数组里的每一个字符转换为int，存入data数组中 } //2.分糖果 int sum[] = new int[arr.length]; Arrays.fill(sum,1);//初始化最少糖果:每个人起码得有1个糖果 for(int i=1;i<arr.length;i++){ if(arr[i]>arr[i-1]){ sum[i]=sum[i-1]+1; }else if(arr[i]==arr[i-1]){//相同个数则糖果数相同 sum[i]=sum[i-1]; } }//从左往右遍历，后者大于前者则后者糖果树+1 for(int i=arr.length-2;i>0;i--){ if(arr[i]>arr[i+1]){ sum[i]=(sum[i]>sum[i+1]+1)?sum[i]:sum[i+1]+1; }else if(arr[i]==arr[i+1]){//相同个数则糖果数相同 sum[i]=sum[i+1]; } }//从右往左遍历，若前者大于后者并且前者糖果数不大于后者，则前者数目为后者+1 //3.打印 int candy=0; for(int i=0;i<sum.length;i++){ candy = candy+sum[i]; } System.out.print(candy); } }
发表于 2019-10-02 17:39:34
回复(0)
N = int(input()) rating = list(map(int, input().split())) candy = [1]*N for i in range(1, N): if rating[i] > rating[i-1]: candy[i] = candy[i-1] + 1 elif rating[i] == rating[i-1]: candy[i] = candy[i-1] for i in range(N-1, 0, -1): if rating[i-1] > rating[i]: candy[i-1] = max(candy[i-1], candy[i]+1) elif rating[i-1] == rating[i]: candy[i-1] = max(candy[i-1], candy[i]) candy[i] = candy[i-1] print(sum(candy))
发表于 2019-08-24 18:56:05
回复(0)
我用了辅助数组，空间复杂度n,向各位请教怎么优化成O(1)
#include<iostream>
#include<vector>
#include<algorithm>
#include <numeric>
using namespace std;
int main()
{
int N;
cin >> N;
vector<int>zq(N), candy(N, 1);//每人分一个
for (int i = 0; i < N; ++i)
cin >> zq[i];
for (int i = 1; i < N; ++i)//全员向左看
{
if (zq[i] > zq[i - 1])
candy[i] = candy[i - 1] + 1;
else if(zq[i] == zq[i - 1])
candy[i] = candy[i - 1] ;
}
for (int i = N - 2; i >= 0; --i)//全员向右看
{
if (zq[i] > zq[i + 1])
candy[i] = max(candy[i], candy[i + 1] + 1);
else if (zq[i] == zq[i + 1])
candy[i] = candy[i + 1];
}
cout << accumulate(candy.begin(), candy.end(), 0) << endl;
return 0;
}
发表于 2019-08-12 10:36:26
回复(0)
问题信息
通过挑战的用户
查看代码-
2023-01-14 17:50:48
-
2022-11-12 16:59:57
-
2022-10-23 17:17:33
-
2022-10-15 14:47:38
-
2022-10-03 20:52:06
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
