题解：P12167 不用二分

· · 题解

开头介绍：

该题解为本蒟蒻第一个题解，不用二分做法，想用二分的见其他题解。

注意：本文中“!”表感叹。

题目分析：

传送门

大概看一下题目就可以知道：其实就是同种颜色的水在倒来倒去。

这里就要注意了：题目中说：

因此他规定如果第 i 个瓶子和第 j 个瓶子中的水颜色相同并且满足 i<j，即可将任意整数单位的水从第 i 个水瓶倒出，倒入第 j 个水瓶中。

所以：只能从左往右倒，不能反过来。

右边的水不能倒过来，就不能增加同种颜色中前 i 个杯子的水的总量。所以，前 i 个水的总量的最大值就是这 i 个数的和。那么，这 i 个数的最小值的最大值就是他们的平均数。

我们找出的数必须满足大于等于所有平均数。所以，这个数就是所有平均数的最小值。

算法解析

首先：我们建一个类，来记录一种颜色中目前的前缀和以及杯子数。

struct Node { //用于表示每种颜色的情况
    long long sum=0,cnt=0; //sum前缀和 cnt数量
} s[M];

接下来，输入 n 和 k 后，按顺序输入每个 a 的值。将 a 加到对应颜色的 sum 中，并使 cnt 加1。

for(int i=1; i<=n; i++) {
    cin>>a[i];
    s[i%k].sum+=a[i];
    s[i%k].cnt++;

最后求出平均值并更新 ans 即可。

完整代码如下：

//luogu P12167
#include <bits/stdc++.h>
using namespace std;
const int M=100010;
struct Node { //用于表示每种颜色的情况
    long long sum=0,cnt=0; //sum前缀和 cnt数量
} s[M];
long long n,k;
long long a[M],ans=1e9;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k;
    for(int i=1; i<=n; i++) {
        cin>>a[i];
        s[i%k].sum+=a[i];
        s[i%k].cnt++;
        ans=min(s[i%k].sum/s[i%k].cnt,ans);
    }
    cout<<ans;
    return 0;
}

复杂度 O(n)， 代码长度应该没有更短的了吧。

交作业