1 条题解

  • 1
    @ 2024-4-2 14:16:39

    这道题和课上的OJ类似,只不过需要求的是最大的区间和,即 max(sum[k],sum[k+1],,sum[k+n1])sum[k1]max(sum[k], sum[k+1], …, sum[k+n-1])-sum[k-1]。一样的思路,先断环为链。然后维护单递减队列,用ans1和ans2分别记录最大心情值和此时开始汇报成绩的次序。注意下这里的ans1初始化一个较小值就好了~

    参考代码
    
    #include<iostream>
    using namespace std;
    int n, head = 1, tail, ans1=-100000,ans2;
    long long a[2000001], sum[2000001], q[2000001];
    int main()
    {
        cin >> n;
        for ( int i = 1; i <= n; i ++)
            cin >> a[i];
        for (int i = 1; i <= n; i ++)
            a[i + n] = a[i];
        for (int i = 1; i <= 2 * n; i ++)
            sum[i] = sum[i - 1] + a[i];
        for (int k = 1; k <= n - 1 ; k ++)
        {
            while (head <= tail && sum[k] >= sum[q[tail]])
                tail--;
            q[++tail] = k;
        }
        for (int k = 1; k <= n ; k ++)
        {
            if (head <= tail && k > q[head])
                head++;
            while (head <= tail && sum[k + n - 1] >= sum[q[tail]])
                tail--;
            q[++tail] = k + n - 1;
            if (sum[q[head]] - sum[k - 1] >= ans1)
                ans1=sum[q[head]] - sum[k - 1],ans2=k;
        }
        cout << ans2 << " " << ans1;
        return 0;
    }
    
    • 1

    信息

    ID
    702
    时间
    1000ms
    内存
    256MiB
    难度
    2
    标签
    (无)
    递交数
    55
    已通过
    35
    上传者