拆分成最多数目的正偶数之和

首先，如果finalSum为奇数，不可能是正偶数之和那么返回空数组
其次，如果finalSum为偶数，那么贪心的从小到大拆分偶数，这样可以保证最多数目，直到剩余数值小于等于当前最大的偶数为止，由于是从小到大贪心的枚举偶数，剩余数值不可能再次拆分，所以如果此时拆分后剩余的finalSum大于零，则将这个数值加到最大的偶整数上，从而保证所有的数互不相同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<long long> maximumEvenSplit(long long finalSum) {
        vector<long long> res; 
        if (finalSum % 2)
            return res;
        for (int i = 2; i <= finalSum; i += 2)
        {
            res.push_back(i);
            finalSum -= i;
        }
        if (finalSum)
            res.back() += finalSum;
        return res;
    }
};

垃圾桶

开两个数组l[]和r[]，分别记录每个房子左边最近的垃圾桶和右边最近的垃圾桶， 最后遍历一遍取最小值即可

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
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 5e5 + 5;
int l[N], r[N];
char s[N];

signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    
    int t;
    cin >> t;
    for (int k = 1; k <= t; k ++)
    {
        int n;
        cin >> n >> s + 1;
        l[0] = -0x3f3f3f3f, r[n + 1] = 0x3f3f3f3f;
        for (int i = 1; i <= n; i ++)
        {
            if (s[i] == '1')
                l[i] = i;
            else
                l[i] = l[i - 1];
        }
        
        for (int i = n; i >= 1; i --)
        {
            if (s[i] == '1')
                r[i] = i;
            else
                r[i] = r[i + 1];
        }
        
        LL ans = 0;
        for (int i = 1; i <= n; i ++)
        {
            ans += min(i - l[i], r[i] - i);
        }
        
        cout << "Case #" << k << ": " << ans << endl;
    }
}