解法：枚举 & 前缀和

为了方便计算前（后）缀和，我们认为 customers 的下标是从 $1$ 开始的，最后答案减 $1$ 即可。

维护 $f(i)$ 表示第 $1$ 到第 $i$ 个字符有几个 N（初值 $f(0) = 0$），$g(i)$ 表示第 $i$ 到第 $n$ 个字符有几个 Y（初值 $g(n + 1) = 0$），那么第 $h$ 小时关店的代价即为 $f(h - 1) + g(h)$。

从 $1$ 到 $(n + 1)$ 枚举所有 $h$ 并选出代价最小的即可。复杂度 $\mathcal{O}(n)$。

参考代码（c++）

###c++

class Solution {
public:
    int bestClosingTime(string customers) {
        int n = customers.size();

        int f[n + 2], g[n + 2];
        // 计算前缀有几个 N
        f[0] = 0;
        for (int i = 1; i <= n; i++) f[i] = f[i - 1] + (customers[i - 1] == 'N' ? 1 : 0);
        // 计算后缀有几个 Y
        g[n + 1] = 0;
        for (int i = n; i > 0; i--) g[i] = g[i + 1] + (customers[i - 1] == 'Y' ? 1 : 0);

        // 枚举答案
        int ans = 0, best = 1e9;
        for (int i = 1; i <= n + 1; i++) {
            int tmp = f[i - 1] + g[i];
            if (tmp < best) ans = i, best = tmp;
        }
        return ans - 1;
    }
};

解法：贪心 & 排序

每次应该选择当前幸福值最高的孩子。由于每个孩子在没被选中时，幸福值都会下降相同的量，所以幸福值的相对大小关系不会改变。

因此将孩子按幸福值从大到小排序，依次选择孩子即可。复杂度 $\mathcal{O}(n\log n)$。

参考代码（c++）

###c++

class Solution {
public:
    long long maximumHappinessSum(vector<int>& happiness, int K) {
        int n = happiness.size();
        // 将孩子按幸福值排序
        sort(happiness.begin(), happiness.end());
        long long ans = 0;
        // 按幸福值从大到小选择孩子
        for (int i = n - 1; i >= n - K; i--) ans += max(0, happiness[i] - (n - 1 - i));
        return ans;
    }
};