4.23 每日一题题解

小阳买水果

题目链接：https://ac.nowcoder.com/acm/contest/949/D

涉及知识点：

前缀和/排序

solution：

(题目是让你输出满足子序列和大于0的最长的连续子序列)
(n很大(2e6)，双重for循环会tle)
(设前缀和数组为pre，如果pre[i] < pre[j](i < j)，意味着[i+1,j]区间和大于0)
(所以做法就是用结构体存一下前缀和以及下标)
(要加个前缀和为0，下标为0，如果只有一个点 1，就没有比较的点了)
(按照前缀和从小到大排序，如果相等按照下标从大到小)
(排完序之后只需要遍历排序后的结构体下标，记录最小值，最大差值即可)

std:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 2e6 + 5;
struct node{
    int x,i;
}a[maxn];
bool cmp(node p1,node p2){
    if(p1.x == p2.x)
        return p1.i > p2.i;
    return p1.x < p2.x;
}
int main()
{
    int n;
    scanf("%d",&n);
    a[n+1].i = 0,a[n+1].x = 0;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i].x);
        a[i].x += a[i-1].x,a[i].i = i;
    }
    n++;
    sort(a+1,a+1+n,cmp);
    int minn = n,ans = 0;
    for(int i=1;i<=n;i++){
        minn = min(minn , a[i].i);
        if(a[i].i > minn)
            ans = max(ans , a[i].i - minn);
    }
    printf("%d
",ans);
     
    return 0;
}