牛客小白月赛16 D 小阳买水果 (思维题)
2024-09-06 00:41:01
链接:https://ac.nowcoder.com/acm/contest/949/D
来源:牛客网
时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld
题目描述
水果店里有 nn个水果排成一列。店长要求顾客只能买一段连续的水果。
小阳对每个水果都有一个喜爱程度 aiai,最终的满意度为他买到的水果的喜欢程度之和。
如果和为正(不管是正多少,只要大于 00 即可),他就满意了。
小阳对每个水果都有一个喜爱程度 aiai,最终的满意度为他买到的水果的喜欢程度之和。
如果和为正(不管是正多少,只要大于 00 即可),他就满意了。
小阳想知道在他满意的条件下最多能买多少个水果。
你能帮帮他吗?
输入描述:
第一行输入一个正整数 n,表示水果总数。 第二行输入 n 个整数 aiai,表示小阳对每个水果的喜爱程度。
输出描述:
一行一个整数表示结果。(如果 1 个水果都买不了,请输出 0)
备注:
1≤n≤2×106,|ai|≤1031≤n≤2×106,|ai|≤103 解题思路:把前缀和从小到大排序,如果前缀和相等把编号大的放前面,然后从前往后遍历,记录遍历过程最小的编号,如果当前的编号大于最小的编号,则更新答案。注意特判n=1的情况就可以了
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e6+;
int n;
struct node{
int pos,num;
}p[maxn];
bool cmp(node a,node b){
if(a.num==b.num) return a.pos>b.pos;
return a.num<b.num;
} int main(){
scanf("%d",&n);
for(int i=;i<=n;i++){
int x;
scanf("%d",&x);
p[i].num=p[i-].num+x;
p[i].pos=i;
}
n++;
int minpos=n;
int ans=;
sort(p+,p+n+,cmp);
for(int i=;i<=n;i++){
minpos=min(minpos,p[i].pos); //记录编号最小的位置
if(minpos<p[i].pos) //当前编号大于记录的最小编号,则更新答案
ans=max(ans,p[i].pos-minpos);
}
printf("%d\n",ans);
return ;
}
最新文章
- connect/express 的参考
- 机械键盘那些事[我用过的minila Filco cherry 3494 阿米洛87]
- Android开发之Canvas rotate方法释疑
- Kernel启动时 驱动是如何加载的module_init,加载的次序如何;略见本文
- qemu 模拟-arm-mini2440开发板-启动u-boot,kernel和nfs文件系统
- Unity 3D 进度条制作
- C++ 多态性浅谈
- 【zkw费用流】[网络流24题]餐巾计划问题
- UVA 673 Parentheses Balance (栈)
- 应对不同格式 轻松转换PDF、WORD、PPT、TXT常用文件
- css文本强制一行 字间距
- C# TextBox 焦点
- webservice生成客户端代码
- zzw原创_mysql脚本打印出提示信息
- BugFree设置邮箱通知(这里以163邮箱为例)
- BZOJ3861 : Tree
- python 中 类型转换 bytes
- 使用express框架和mongoose在MongoDB新增数据
- springBoot的搭建使用记录
- 开源项目PullToRefresh详解(二)——PullToRefreshGridView
热门文章
- hdu 6134: Battlestation Operational (2017 多校第八场 1002)【莫比乌斯】
- vue的响应接口
- Graph Convolutional Network
- 进入cmd的另外的一种方式
- [CF959E]Mahmoud and Ehab and the xor-MST题解
- pycharm默认的模板修改python script
- ZOJ 3822 ( 2014牡丹江区域赛D题) (概率dp)
- 北风设计模式课程---状态模式State(对象行为型)
- Gradle查看Project中的所有 Task
- RabbitMq(7)消息延时推送