牛客小白月赛16小阳买水果(前缀和+贪心)

el/2024/5/23 2:34:10

链接:https://ac.nowcoder.com/acm/contest/949/D
来源:牛客网
 

题目描述

水果店里有 nnn个水果排成一列。店长要求顾客只能买一段连续的水果。
小阳对每个水果都有一个喜爱程度 aia_iai​,最终的满意度为他买到的水果的喜欢程度之和。
如果和为正(不管是正多少,只要大于 000 即可),他就满意了。

小阳想知道在他满意的条件下最多能买多少个水果。

你能帮帮他吗?

输入描述:

第一行输入一个正整数 n,表示水果总数。第二行输入 n 个整数 aia_iai​,表示小阳对每个水果的喜爱程度。

输出描述:

一行一个整数表示结果。(如果 1 个水果都买不了,请输出 0)

示例1

输入

复制

5
0 0 -7 -6 1

输出

复制

1

备注:

1≤n≤2×106,∣ai∣≤1031 \leq n \leq 2 \times 10^6,|a_i| \leq 10^31≤n≤2×106,∣ai​∣≤103

思路:

前缀和排序,记录下标,那么必定后面的减去前面的是大于等于0的,

1、避免相减等于零,我们可以让id大的放到前面,就不会走max这一步

2、可能出现某一个前缀本身就是最长解,只需加上一个起始点,参与排序就行,减去起始点之后还是本身,

 

必须要满足左端点必须最小,右端点必须在左端点的右边,且尽量大

 

code:
 

#include<bits/stdc++.h>
using namespace std;const int inf = 0x3f3f3f3f;struct node
{int sum,id;bool operator < (const node &t) const{if(sum == t.sum ) return id > t.id; //避免两个0相减的情况return sum < t.sum;}
}a[2000010];int min_id = inf;
int ans = 0;int main()
{int n,x;cin>>n;for(int i = 1;i <= n; i++){cin >> x;a[i].sum = a[i-1].sum + x;a[i].id = i;}sort(a , a+n+1);//起始点参与排序 for(int i = 0; i <= n; i++){if(a[i].id < min_id)//更新当前最小id min_id = a[i].id;else  //更新答案 ans = max( ans , a[i].id - min_id );}cout<<ans;return 0;
}

 


http://www.ngui.cc/el/3419481.html

相关文章

牛客小白月赛16 小雨的矩阵 (暴力搜索)

链接&#xff1a;https://ac.nowcoder.com/acm/contest/949/E 来源&#xff1a;牛客网 时间限制&#xff1a;C/C 1秒&#xff0c;其他语言2秒 空间限制&#xff1a;C/C 262144K&#xff0c;其他语言524288K 64bit IO Format: %lld 题目描述 小雨有一个 nnn \times nnn 的矩…

牛客小白月赛16 小石的妹子 (贪心 )

链接&#xff1a;https://ac.nowcoder.com/acm/contest/949/F 来源&#xff1a;牛客网 小石的妹子 时间限制&#xff1a;C/C 1秒&#xff0c;其他语言2秒 空间限制&#xff1a;C/C 262144K&#xff0c;其他语言524288K 64bit IO Format: %lld 题目描述 小石有 n 个妹子&a…

牛客 回文数(模拟 )

链接&#xff1a;https://ac.nowcoder.com/acm/contest/1071/A 来源&#xff1a;牛客网 题目描述 今年是国际数学联盟确定的“2000——世界数学年”&#xff0c;又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛&#xff0c;组织了一场别开生面的数学…

牛客Game with numbers(暴力)

链接&#xff1a;https://ac.nowcoder.com/acm/contest/942/B 来源&#xff1a;牛客网 时间限制&#xff1a;C/C 1秒&#xff0c;其他语言2秒 空间限制&#xff1a;C/C 262144K&#xff0c;其他语言524288K 64bit IO Format: %lld 题目描述 给定大小为n{n}n的集合S{S}S 一…

Andrew算法——凸包问题

Andnew算法是Graham扫描法的变种 步骤&#xff1a; 把所有点优先按照横坐标x从小到大排序&#xff0c;如果x坐标相等&#xff0c;则按照y坐标从小到大排序去除重复的点&#xff0c;&#xff08;unique函数好评&#xff09;从左到右扫描下凸包&#xff0c;把满足条件的点放入b…

hdu 6546 Function(贪心+堆优化)

Function Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others) Total Submission(s): 278 Accepted Submission(s): 106 Problem Description wls 有 n 个二次函数 Fi (x ) ai x2 bi x ci (1 ≤ i ≤ n ). 现在他想在∑ni1 xi m …

结构体重载输入输出运算符

可以直接输入结构体&#xff0c;顺便初始化&#xff1b; #include<bits/stdc.h> using namespace std;struct node {int x, y, z;friend istream & operator >> (istream&, node &t){cin >> t.x >> t.y;t.z 1; //顺便初始化z return cin…

牛客训练哈希专题-矩阵 ( 哈希+二分 )

链接&#xff1a;https://ac.nowcoder.com/acm/problem/13610 来源&#xff1a;牛客网 矩阵 时间限制&#xff1a;C/C 1秒&#xff0c;其他语言2秒 空间限制&#xff1a;C/C 131072K&#xff0c;其他语言262144K 64bit IO Format: %lld 题目描述 给出一个n * m的矩阵。让…

Fancy Signal Translate(思维)

链接&#xff1a;https://ac.nowcoder.com/acm/contest/16/D 来源&#xff1a;牛客网 Fancy Signal Translate 时间限制&#xff1a;C/C 1秒&#xff0c;其他语言2秒 空间限制&#xff1a;C/C 131072K&#xff0c;其他语言262144K 64bit IO Format: %lld 题目描述 FST是一…

hdu 1263 水果 (map)

水果 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 15438 Accepted Submission(s): 5999 Problem Description 夏天来了~~好开心啊,呵呵,好多好多水果~~ Joe经营着一个不大的水果店.他认为生存之道就是…