陌

用户名：lzy599

访问量：6561

签　名：

哪有什么签名

等　　级
排　　名	553
经　　验	4216
参赛次数	14
文章发表	12
年　　龄	0
在职情况	学生
学　　校	福建农林大学东方学院
专　　业

　　自我简介：

TA的其他文章

[传智杯]程序员节发橙子（C++代码）（简短+双指针+图示）
浏览：596

[传智杯]众数出现的次数-题解(C++代码)（简短+易懂）
浏览：304

蓝桥杯2019年第十届真题-完全二叉树的权值-题解(C++代码)（前缀和+简短 +图解）
浏览：881

你可能喜欢

C语言程序设计教程（第三版）课后习题8.6 （C++代码）不是所有的时候都要按照题目要求才能AC

[传智杯]程序员节发橙子（C++代码）（简短+双指针+图示）

　　作者: 陌　　　　发表时间：2020-04-12 12:31:57 浏览：596　|　评论：2　

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

## 思路
**分为两种情况，以及特殊处理**
**两种情况：**
-  **递增**
	当后面数比前面数大的时候就直接在前数的基础上+1;
-  **递减**
	因为不知道递减区间每一个区间有多少个数，所以先求出递减区间的头尾。
	> 通过两个指针
	> st：表示递减区间的头
	> ed：表示递减区间的尾
	
	如果遇到递减的情况，通过循环，先求出ed的位置
	然后再从尾到头按照递增情况处理就可以了
	
**特殊情况：**
- 如果相邻两个区间，递减区间的数量大于或等于递增区间：
 > 增区间的尾 <= 减区间的头		（橙子数）
 
	可是往回想，增区间尾的分数大于减区间头的分数，所以，增区间的尾永远比减区间的头大1
	
**图示：**
![特殊情况说明](/image_editor_upload/20200412123127_31351.png "特殊情况说明")

## 代码如下：

```
#include<iostream>
using namespace std;

const int N = 1e6 + 10;
int n , stu[N],q[N];
long long  res = 0;

int main()
{
    scanf("%d",&n);
    for(int i = 1; i <= n; i ++ )scanf("%d",&stu[i]);
	
	//定义双指针，记录头尾
    int st,ed;
    for(int i = 1; i <= n; i ++)
    {
		//递增情况
        if(stu[i] > stu[i-1])
			q[i] = q[i-1] + 1;
			//相等情况
			else if(stu[i] == stu[i-1])
            	q[i] = q[i-1];
        		else
				{
					st = ed = i;//初始化指针
					while(stu[ed] < stu[ed-1] && ed <=n)//双指针：寻找尾指针
					ed++;
					
					for(int j = ed-1; j >= st; j --)//逆方向递增
					q[j] = q[j+1] + 1;

if(q[st] >= q[st-1])q[st-1] = q[st]+1;//特殊情况
					i = ed-1;//更新
				}

}
    for(int i = 1; i <= n; i ++)
        res += q[i];
    printf("%ld\n",res);
    return 0;
}
```

0.0分

8 人评分

C语言网推出会员服务，提供C/C++/算法/Python等多套视频学练课程+源码资源社群答疑+私活推荐等资源，享受丰富的技术学习到变现的乐趣，以含金量和学习效果勇敢挑战同类辅导！点击了解开通

　　评论区

Patient

这细节确实挺多的，挺强的！

2020-11-18 20:19:40

韩汶橦

666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666

2020-11-13 20:13:04

陌

TA的其他文章

你可能喜欢

弟弟的作业（C语言代码）

【亲和数】（C语言代码）

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

C语言程序设计教程（第三版）课后习题8.6 （C++代码）不是所有的时候都要按照题目要求才能AC

printf基础练习2 （C语言代码）

[传智杯]程序员节发橙子（C++代码）（简短+双指针+图示）

评论区

精彩推荐

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

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

C二级辅导-同因查找（C语言代码）

C二级辅导-公约公倍（C语言代码）

分糖果（C++代码）

多输入输出练习1 （C语言代码）

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

WU-蓝桥杯算法提高VIP-勾股数（C++代码）

本人酷爱递归实现很多问题，这里也是

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

陌

TA的其他文章

你可能喜欢

弟弟的作业 （C语言代码）

【亲和数】 （C语言代码）

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

C语言程序设计教程（第三版）课后习题8.6 （C++代码）不是所有的时候都要按照题目要求才能AC

printf基础练习2 （C语言代码）

[传智杯]程序员节发橙子 （C++代码）（简短+双指针+图示）

评论区

精彩推荐

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

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

C二级辅导-同因查找 （C语言代码）

C二级辅导-公约公倍 （C语言代码）

分糖果 （C++代码）

多输入输出练习1 （C语言代码）

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

WU-蓝桥杯算法提高VIP-勾股数 （C++代码）

本人酷爱递归实现很多问题，这里也是

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

弟弟的作业（C语言代码）

【亲和数】（C语言代码）

[传智杯]程序员节发橙子（C++代码）（简短+双指针+图示）

　　评论区

C二级辅导-同因查找（C语言代码）

C二级辅导-公约公倍（C语言代码）

分糖果（C++代码）

WU-蓝桥杯算法提高VIP-勾股数（C++代码）