主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
题解 P6364 【1024 程序员节发橙子】
最后更新于 2025-07-31 10:34:28
作者
sysong
分类
题解
题解
P6364
复制 Markdown
查看原文
删除文章
更新内容
## 一道简单模拟(贪心)题。 ------------ ## 思路(策略) 1. 如果当前人分数与之前一人一样,那么橘子数相等。 2. 如果比之前一人分数高(**递增**),那么橘子数为之前一人的橘子数加一。 3. 由于分数可能出现**长度大于$2$的递减序列**,所以最后还要反过来扫一遍数组,把橘子数加上去。(~~卡了我一次~~) # 注意:要开$long long$!(值域最大为$1e9$) ------------ ## 下面上代码(注释在里面) ```c++ #include <bits/stdc++.h> #define R register #define gc() getchar() #define ll long long using namespace std; inline ll rd(){ R ll x=0;R char c=gc(); while(c>'9'||c<'0')c=gc(); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=gc(); return x; }//快读函数,没什么好说的(不用也行) ll h[1000001],s[1000001]={0,1};//h数组存分数,s数组存橘子数 int main(){ R ll n=rd(),ans=1;//答案初始为一(第一个人) h[1]=rd(); for(R ll i=2;i<=n;i++){//一边读入一边计算递增部分,稍微快一点 h[i]=rd(); if(h[i]>h[i-1]) s[i]=s[i-1]+1,ans+=s[i];//比前一人分数高 else if(h[i]==h[i-1]) s[i]=s[i-1],ans+=s[i];//一样 else s[i]=1,ans++;//比前一人低,初始化为一,后面再处理 } for(R ll i=n,pre;i>=1;i--) if(h[i-1]>h[i])//出现递减 pre=s[i-1],//存储增加之前的橘子数 s[i-1]=max(s[i-1],s[i]+1),//增加后的值取他本身和他下一个加一两个数的最大值 ans+=s[i-1]-pre;//更新答案(之所以不直接加一是因为递减序列长度可能大于二,又卡我一次) printf("%lld\n",ans); return 0; } ``` 写的够清楚了吧 谢谢观看!(~~留个赞呗~~) 如有问题,欢迎提出!
正在渲染内容...
点赞
0
收藏
0