一群孩子做游戏，现在请你根据游戏得分来发糖果，要求如下：
1. 每个孩子不管得分多少，起码分到一个糖果。
2. 任意两个相邻的孩子之间，得分较多的孩子必须拿多一些糖果。(若相同则无此限制)
给定一个数组arr代表得分数组，请返回最少需要多少糖果。
[编程题]分糖果问题
#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;
for(int i=n-2;i>=0;i--)
if(a[i]>a[i+1])
b[i] = max(b[i], b[i+1]+1);
for(int i=0;i<n;i++)
s += b[i];
cout<<s<<endl;
return 0;
}
发表于 2020-03-21 23:27:20
回复(0)
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
vector<int>num(n),num1(n,1);
for(int i=0;i<n;i++)
cin>>num[i];
for(int i=1;i<n;i++)
{
if(num[i]>num[i-1])
num1[i]=num1[i-1]+1;
}
for(int i=n-2;i>=0;i--)
{
if(num[i]>num[i+1])
num1[i]=max(num1[i],num1[i+1]+1);
}
cout << accumulate(num1.begin(),num1.end(),0) << endl;
return 0;
}
发表于 2019-09-08 22:31:11
回复(0)
贪心算法：从左往右检查一遍，从右往左再检查一遍，以最小限度超越旁边分数比自己低且糖果还比自己多的小朋友
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;
}
// 从右往左
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;
}
int total = 0;
for(int i = 0; i < n; i++) total += candy[i];
System.out.println(total);
}
}
编辑于 2021-06-29 16:19:01
回复(0)
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
vector<int>num(n),num1(n,1);
for(int i=0;i<n;i++)
cin>>num[i];
for(int i=1;i<n;i++)
{
if(num[i]>num[i-1])
num1[i]=num1[i-1]+1;
}
for(int i=n-2;i>=0;i--)
{
if(num[i]>num[i+1])
num1[i]=max(num1[i],num1[i+1]+1);
}
cout << accumulate(num1.begin(),num1.end(),0) << endl;
return 0;
}
using namespace std;
int main()
{
int n;
cin>>n;
vector<int>num(n),num1(n,1);
for(int i=0;i<n;i++)
cin>>num[i];
for(int i=1;i<n;i++)
{
if(num[i]>num[i-1])
num1[i]=num1[i-1]+1;
}
for(int i=n-2;i>=0;i--)
{
if(num[i]>num[i+1])
num1[i]=max(num1[i],num1[i+1]+1);
}
cout << accumulate(num1.begin(),num1.end(),0) << endl;
return 0;
}
发表于 2022-10-25 20:21:07
回复(0)
运行时间：428ms 占用内存：95064KB
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int length = in.nextInt();
if(length <= 0) {
return;
}
int[] score = new int[length];
int[] candy = new int[length];
for(int i = 0; i < length; i++) {
score[i] = in.nextInt();
}
for(int i = 1; i < length; i++){
if(score[i] > score[i-1]) {
candy[i] = candy[i-1] + 1;
}
}
for(int j = length -2; j >= 0; j--) {
if(score[j] > score[j+1]) {
candy[j] = Math.max(candy[j], candy[j+1] + 1);
}
}
int result = length;
for(int i = 0; i < length; i++) {
result += candy[i];
}
System.out.print(result);
}
} 代码已通过，仅供参考。
编辑于 2021-05-25 21:06:36
回复(0)
#include<iostream>
#include<vector>
using namespace std;
class Solution{
public:
int getMinCandy(vector<int> arr){
if(arr.size() == 0)
return 0;
vector<int> left(arr.size(),1);
vector<int> right(arr.size(),1);
//从左到右遍历 满足左原则
for(int i = 1;i<arr.size();i++){
if(arr[i] > arr[i-1]){
left[i] = left[i-1] + 1;
}
}
//从右向左遍历 满足右原则
for(int i = arr.size() -2;i>=0;i--){
if(arr[i] > arr[i+1]){
right[i] = right[i+1]+1;
}
}
int res = 0;
for(int i=0;i<arr.size();i++){
res += max(left[i],right[i]);
}
return res;
}
};
int main(){
int N;
cin>>N;
vector<int> arr(N);
for(int i=0;i<N;i++)
cin>>arr[i];
Solution c1;
cout<<c1.getMinCandy(arr)<<endl;
return 0;
}
#include<vector>
using namespace std;
class Solution{
public:
int getMinCandy(vector<int> arr){
if(arr.size() == 0)
return 0;
vector<int> left(arr.size(),1);
vector<int> right(arr.size(),1);
//从左到右遍历 满足左原则
for(int i = 1;i<arr.size();i++){
if(arr[i] > arr[i-1]){
left[i] = left[i-1] + 1;
}
}
//从右向左遍历 满足右原则
for(int i = arr.size() -2;i>=0;i--){
if(arr[i] > arr[i+1]){
right[i] = right[i+1]+1;
}
}
int res = 0;
for(int i=0;i<arr.size();i++){
res += max(left[i],right[i]);
}
return res;
}
};
int main(){
int N;
cin>>N;
vector<int> arr(N);
for(int i=0;i<N;i++)
cin>>arr[i];
Solution c1;
cout<<c1.getMinCandy(arr)<<endl;
return 0;
}
发表于 2020-05-25 12:05:16
回复(0)
import java.util.Arrays;
import java.util.Scanner;
import java.util.Scanner;
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;
}
}
//左看一下，发现比自己小且糖果比自己多的，就比小的多一个
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;
}
}
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;
}
}
//左看一下，发现比自己小且糖果比自己多的，就比小的多一个
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;
}
}
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 12:02:37
回复(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{
add = 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{
add = 1;
}
temp = arr[i];
ans += max(left[i], right[i]);
}
printf("%d", ans);
return 0;
}
发表于 2020-02-13 14:12:08
回复(0)
#include<stdio.h>
int main()
{
int n;
scanf("%d",&n);
int m[n];
for(int i=0;i<=n-1;i++)
{scanf("%d",&m[i]);
};
int c[n],i,c2[n];
for(i=0;i<=n-1;i++)
{c[i]=1;
c2[i]=1;
};
for( i=0;i<n-1;i++)//向右
{if((m[i+1]>m[i]))
{c[i+1]=c[i]+1;}
};
for(i=n-1;i>0;i--)//向左
{if((m[i-1]>m[i]))
{c2[i-1]=c2[i]+1;}
}
for( i=0;i<=n-1;i++)//避免中间不一致
{ if((c2[i]>c[i]))
{ c[i]=c2[i];}
}
int s=0;
for( i=0;i<=n-1;i++)
{ s = s+c[i];}
printf("%d",s);
return 0;
}
发表于 2019-09-12 19:51:05
回复(0)
辅助用了candy数组，空间复杂度n，不知道如何改成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;//全员向左看
for (int i = N-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:22:58
回复(0)
问题信息
通过挑战的用户
查看代码-
2023-01-14 17:15:55
-
2022-11-12 16:58:49
-
2022-10-24 21:48:42 -
2022-10-24 20:41:45 -
2022-10-24 20:28:49
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
