Rating System

发表于 分类于 阅读次数： 1

D. Rating System

正解写挂不要太典

题面

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

做法一

官方做法 假设最终的答案是 k，那么一定可以找出一个区间 [l,r]，使得在题目的规则下 ratingl=ratingr=k，并且区间和小于零，这段区间就是对答案贡献最大的区间（因为对答案的贡献相当于加上被减掉的这部分）。 Prof. 显然 ratingl=k,ratingr≥k。若 ratingr>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;
}