ISSAC

用户名：uq_50089742160

访问量：5766

签　名：

等　　级
排　　名	705
经　　验	3912
参赛次数	8
文章发表	8
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

信息学奥赛一本通T1311-求逆序对-题解（C++代码）
浏览：2067

你可能喜欢

[传智杯]程序员节发橙子-题解(C++代码)

　　作者: ISSAC　　　　发表时间：2020-04-11 21:02:57 浏览：410　|　评论：0　

原题链接：[传智杯]程序员节发橙子

#[传智杯]程序员节发橙子

时间限制: 2Sec 内存限制: 512MB 提交: 502 解决: 33

题目描述
每年的 1024 程序员节日，黑马程序员都会举办大型的庆祝活动。今年的程序员节也不例外，每个班级的同学都发了橙子。

班级里有 n 名同学从前到后排成一排，且已经得知了这些同学的成绩，其中第 i 名同学的成绩是 ai。班主任想根据同学们上个阶段的考试成绩来评定发橙子的数量。为了激励成绩优秀同学，发橙子时需要满足如下要求：

相邻同学中成绩好的同学的橙子必须更多。若相邻的同学成绩一样，则它们分到的数量必须平等。
每个同学至少分配一个橙子
由于预算有限，班主任希望在符合要求的情况下发出尽可能少的橙子。请问，至少需要准备多少橙子呢？

输入
第一行是一个不超过 10^6 正整数 n，表示学生数量。

接下来一行有 n 个不超过 10^9 的非负整数 ai，表示第 i 个同学的成绩。

输出
输出答案，也就是需要最少准备多少个橙子。
样例输入
5
3 4 5 4 3
样例输出
9

我的思路是，这道题无非就两种情况，递增序列和递减序列，例如3，4，5是增序列，5，4，3是减序列，当然，若出现相同的数字，我们把它当为一个数看，我们把最大值5都记录在两个序列中，增序列的情况很简单，就下一个发的数量比上一个的人多一个就行了。关键是减序列，他又分为两种情况，一种是减序列的个数比增序列少的情况，还有一种就是减序列的数目比增序列多的情况，这时最大值开始假设发的橙子数就发生了变化，变为了假减序列的个数加1.

```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define Maxsize 1000005
typedef long long ll;
using namespace std;
int minx=0;//记录减序列一共的个数（包括重复的数字）易得减序列的个数等于减序列所有的数减去重复的个数：即minx-chong；
int chong=0;//记录减序列重复个数
int flag=0;//记录是否进入减序列
ll node; //记录最大值的假设橙子个数
ll value[Maxsize];
int n;
int main()
{   int cnt=0; //这个记录的是当前假设发橙子的个数
	memset(value,0,sizeof(value));
	cin>>n;
	ll sum=0;
	for(int i=1;i<=n;i++)
	{
		cin>>value[i];
		if(value[i]>value[i-1])//当进入增序列，则所有减序列的状态清零
		{   chong=0;
		    minx=0; //减序列的个数
		    flag=0;
			cnt++;  //发的橙子应该比上一个的人多
			sum+=cnt; //加起来
		}
		else if(value[i]==value[i-1]) //当相等的情况时
		{
			if(minx!=0) 
			{
			chong++;
			minx++;}
			sum+=cnt;
		}
		else   //是减序列的情况
		{   if(flag==0)//是否是刚进入减序列
		   {
			flag=1; //进入减序列状态
			node=cnt; //把最大值假设发的橙子数记录
			}  
			cnt=1;//将刚进来的数的发橙子数设为1；
		    minx++;
		    	if(minx-chong+1>node)//如果减序列的个数+1大于了最大值
		    	{
		    		sum-=node;
		    		node=minx-chong+1;
		    		sum+=node;
		    	     sum+=minx;//这里为什么是sum+minx呢，因为减序列每加入一个数前面所有减序列的假设值都要+1；
		    	     continue;
			}
			sum+=minx;
			}
	}
	cout<<sum;
	return 0;
}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

ISSAC

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

开心的金明（C++代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

[传智杯]程序员节发橙子-题解(C++代码)

评论区

精彩推荐

【绝对值排序】（C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

校门外的树（C语言代码）

C语言训练-求1+2!+3!+...+N!的和（C语言代码）万恶的long long

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

简单的a+b （C语言代码）

用筛法求之N内的素数。（C++代码）

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

蛇行矩阵（C语言代码）

ISSAC

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

开心的金明 （C++代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

[传智杯]程序员节发橙子-题解(C++代码)

评论区

精彩推荐

【绝对值排序】 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

校门外的树 （C语言代码）

C语言训练-求1+2!+3!+...+N!的和 （C语言代码）万恶的long long

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

简单的a+b （C语言代码）

用筛法求之N内的素数。 （C++代码）

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

蛇行矩阵 （C语言代码）

开心的金明（C++代码）

　　评论区

【绝对值排序】（C语言代码）

校门外的树（C语言代码）

C语言训练-求1+2!+3!+...+N!的和（C语言代码）万恶的long long

用筛法求之N内的素数。（C++代码）

蛇行矩阵（C语言代码）