Rating System

发表于 分类于 阅读次数：

D. Rating System

正解写挂不要太典

题面

https://codeforces.com/contest/1845/problem/D

做法一

官方做法 假设最终的答案是 $k$，那么一定可以找出一个区间 $[l,r]$，使得在题目的规则下 $rating_l = rating_r = k$，并且区间和小于零，这段区间就是对答案贡献最大的区间（因为对答案的贡献相当于加上被减掉的这部分）。 $Prof.$ 显然 $rating_l = k, rating_r \ge k$。若 $rating_r > k$ 那么必然在原序列中存在一段区间和大于 的区间，这段区间被包括在 $[l,r]$，那么这段区间对答案的贡献一定不是最大的。 因此我们只要找到区间和最小的一段区间，$k$ 即为左端点 $l$ 前的前缀和。 代码见官方题解

做法二

考场上写挂的做法，其实只有一个细节要处理。 显然 $k$ 应该是原序列的前缀和序列中的一项 $sum[i]$，满足 $sum[j] < sumi$，当 $k$ 取 $sum[i]$ 时的贡献即为 $sum[i]-min(sum[j])(j \ge i)$ 特殊情况：原始序列 $-1 \ 3$。 解决方法：只需要在原始序列前添加一项 $0$ 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <cstdio>

int t;
int n;
long long a[300005];
long long smin[300005];

long long min(long long a,long long b)
{
    return a<b?a:b;
}

int main()
{
    scanf ("%d",&t);
    while (t--)
    {
        scanf ("%d",&n);
        for (int i=1;i<=n;i++)
            scanf ("%lld",&a[i]);
        for (int i=1;i<=n;i++)
            a[i]+=a[i-1];
        long long ans=0,m=0;
        smin[n]=a[n];
        for (int i=n-1;i>=0;i--)
            smin[i]=min(a[i],smin[i+1]);
        for (int i=0;i<=n;i++)
        {
            long long minn=smin[i];
            if (a[n]+a[i]-minn>ans)
            {
                ans=a[n]+a[i]-minn;
                m=a[i];
            }
        }
        printf ("%lld\n",m);
    }
    return 0;
}