clean code

i create stuff

HackerRank Maximise Sum题解

| Comments

今晚被这道题折磨了好久，记录下。

题意

对数组的子序列（任意相连的元素）求和，找出所有和里对M的模中的最大值。

思路

开始就想到能不能按照“最大子序列和问题”的思路解决，后来发现无论是分治递归求解还是复杂度为O(N)的算法在这个问题中都没有用，于是看了题解。
在Quora上找到了题解，看了半天才看明白。大意是，对于输入的数组v中的元素v[i]，先找到v[i]之前所有数的和对M取模的值（包括v[i]），存到数组prefix中。这里有个技巧，

1
2
3
4
5
6

ull tmp = 0;  // unsigned long long
for (size_t i=0; i<v_size; ++i) {
    tmp += v[i];
    tmp %= m;
    prefix.push_back(tmp);
}

即v[i] = (prefix[i-1] + m) % m。
对于新的数组prefix，保存了当前元素之前所有元素和除m的余数，对于prefix[i]，如果存在j < i，使prefix[j] < prefix[i]，则从j到i的这一段序列肯定不是我们想要的，这段子序列之和对m取模的值为prefix[i]-prefix[j]。所以我们要找出从prefix[0]到prefix[i-1]中比prefix[i]大的。我们需要维护一个有序数组，并且要不断往其中添加元素，C++的set由红黑树实现（题解中介绍），采用之。由于是有序的，只要找到递增数组中比prefix[i]大的第一个元素即可，即这个元素比prefix[i]大得越少越好，使用s.upper_bound(prefix[i])找出这里的迭代器。
代码贴出来：

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
41
42
43
44
45
46
47
48
49
50
51

#include <cstdio>
#include <vector>
#include <set>

using namespace std;

typedef unsigned long long ull;

ull find_result(const vector<ull> &v, ull m) {
    vector<ull> prefix;
    set<ull> s;

    // get prefix array
    size_t v_size = v.size();
    ull tmp = 0;
    for (size_t i=0; i<v_size; ++i) {
        tmp += v[i];
        tmp %= m;
        prefix.push_back(tmp);
    }

    ull res = 0;
    for (size_t i=0; i<v_size; ++i) {
        auto it = s.upper_bound(prefix[i]);
        if (it != s.end()) {
            tmp = (prefix[i] - *it + m) % m;
            res = max(res, tmp);
        }
        s.insert(prefix[i]);
        res = max(res, prefix[i]);
    }
    return res;
}

int main()
{
    int cnt;
    scanf("%d", &cnt);
    vector<ull> v;
    ull n, m, tmp;
    for (int i=0; i<cnt; ++i) {
        scanf("%llu %llu", &n, &m);
        v.clear();
        for (int j=0; j<n; ++j) {
            scanf("%llu", &tmp);
            v.push_back(tmp);
        }
        printf("%llu\n", find_result(v, m));
    }
    return 0;
}

关于C++的部分

看题解新学的set容器

set即集合，维护一个递增数组，两种方法注意下

1
2
3
4
5
6

set<int> s;
s.insert(1);
s.insert(2);
s.insert(3);
auto it = s.upper_bound(2);
cout << *it << endl;  // 输出3

upper_bound(val)[http://www.cplusplus.com/reference/set/set/upper_bound/]函数返回比val大的第一个元素的迭代器，要注意与s.end()比较下，看是否不存在比它大的元素。类似的函数还有lower_bound(val)

vector一定要清空！！！

第一次交全没过！下了测试例子发现从第二组例子开始就没过了，仔细检查发现是vector没有清空搞的鬼，一堆超时的。从另一个角度也说明vector确实牛逼，被我塞了那么多组测试也没爆。。。

总之多做题、多总结吧，想不出来看题解也是好的。

Comments