题解：P12167 不用二分

开头介绍：

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

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

题目分析：

传送门

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

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

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

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

右边的水不能倒过来，就不能增加同种颜色中前

i

个杯子的水的总量。所以，前

i

个水的总量的最大值就是这

i

个数的和。那么，这

i

个数的最小值的最大值就是他们的平均数。

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

算法解析

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

CPP

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

接下来，输入

n

和

k

后，按顺序输入每个

a

的值。将

a

加到对应颜色的

sum

中，并使

cnt

加1。

CPP

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

最后求出平均值并更新

ans

即可。

完整代码如下：

CPP

//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)

，代码长度应该没有更短的了吧。

交作业

题解：P12167 不用二分

文章操作

开头介绍：

题目分析：

算法解析

相关推荐

评论

题解：P12167 不用二分