又不会做的一道C++的题

Question

备战安庆市赛，有一题自己不知道怎么做：

自己觉得用DFS和BFS，可是又不知怎么写……

Answer 1

体力和最小的小组的体力和小于等于各小组体力和的平均值，也就是所有人的体力和除以K，可以利用这个优化。
下面的代码是凭直觉写的：

#include<iostream>

#define N_MAX 30000
#define K_MAX 1000
#define min(a,b) (a<b?a:b)

unsigned int s[N_MAX+1];
unsigned int d[K_MAX+1];

int main() {
    unsigned int N, K, i, ave, max, m;
    std::cin >> N >> K;
    s[0] = 0;
    for (i = 1; i <= N; i++) {
        std::cin >> s[i];
        s[i] += s[i - 1];
    }
    ave = (s[N]+K-1) / K;
    d[0] = 0;
    for (i = 1; i < K; i++) {
        for (d[i] = d[i - 1] + 1; s[d[i]] - s[d[i - 1]] < ave && d[i] < N; d[i]++);
    }
    d[K] = N;
    max = s[N] - s[d[K - 1]];
    for (i = K - 1; i > 0; i--) {
        while (s[d[i + 1]] - s[d[i]] < ave && d[i] > 0) {
            d[i]--;
            m = min(s[d[i + 1]] - s[d[i]], s[d[i]] - s[d[i - 1]]);
            if (max < m)max = m;
            break;
        }
    }
    std::cout << max;
    return 0;
}