题解 | #牛牛晾衣服#

题意整理：

基本题意

给出一个长度为 $n$ 的整数数列 $a_1,a_2,...a_n$ 。

每次操作可以做以下操作中的一个：

让所有 $a_i$ 都减 $1$ 。
选择一个 $j\in [1,n]$ ，让 $a_j$ 减少 $k$ ，剩余的 $a_i(i\ne j)$ 都减少 $1$ 。

如果一个数减少到 $0$ 了知乎再被减少，则依然将它视为 $0$ 。

问最少操作多少次可以使得整个数列不存在正数。

数据范围与性质

$1\le n \le 10^5, 1\le a_i,k \le 10^9$ 。

解法1：枚举答案

【知识点】枚举

【算法】枚举+检验

分析与算法描述

值得注意的是，把任何一个第一种操作用第二种操作取代，效果一定不比第一种操作劣，因此我们可以认为只有第二种操作。

我们考虑把最优性问题转换成判定性问题，从小到大枚举一个次数 $m$ ，检验 $m$ 次操作能否达成目标，如果检验成功，那么就找到了答案。

当次数 $m$ 确定的时候，说明每个数字都至少减少了 $m$ ，于是我们可以先把所有的 $a_i$ 变成 $\max(a_i-m,0)$ 。

而我们操作的时候，除了所有数字都减少 $1$ ，我们可以选一个数字，让它再次减少 $k-1$ 的值。

剩余的非零数字，我们每次只能分配一个大小为 $k-1$ 的减少量给其中一个数字，因此每个数字需要分配 $\lceil\frac{a_i}{k-1}\rceil$ 次操作。所以，只要这时候满足 $\sum _{i=1}^n\lceil\frac{a_i}{k-1}\rceil \le m$ ，那么操作次数 $m$ 就是可行的，否则是不行的。

注意这个算法需要特判 $k=1$ 的情况，因为 $k-1=0$ 的时候上述计算公式没有意义。这时候答案就是 $\max\{a_i\}$ 。

举个例子，对于样例：

n=3,
a=[2,3,9],
k=5

刚开始 $a_i$ 数组是这样的：

图片说明

当取 $m=2$ 的时候，全部减去 $2$ ：

图片说明

可以发现，剩下的部分至少需要 $4$ 次操作， $4>m=2$ 因此这种情况不行。

这样因为需要枚举 $m$ ，而 $m$ 最大可达 $\max\{a_i\}$ ，每次检验还需要遍历枚举 $n$ 个数，因此时间复杂度 $O(n\cdot \max(a_i))$ 。

空间复杂度只需要 $O(n)$ 。

参考代码（会超时）

class Solution {
public:

    bool check(int m,vector<int>& a,int k)//验证答案的合法性
    {
        long long need=0;//用于累加计算需要的最少操作数
        for(int i=0;i<a.size();i++)
        {
            int v=a[i];
            v=max(v-m,0);
            need += ceil(v*1.0/(k-1));
        }
        return m>=need;
    }

    int dryClothes(int n, vector<int>& a, int k) {
        int max_a=0;
        for(auto &i:a)
            max_a=max(max_a,i);//取a中最大值
        if(k==1)//特判k=1的情况
            return max_a;
        for(int m=1;m<=max_a;m++)//枚举答案
            if(check(m,a,k))
                return m;
        return -1;
    }
};

解法2：二分答案

【知识点】二分查找

【算法】二分+检验

实现与分析

我们考虑如何优化上面的做法。

值得的注意一个性质：

如果 $x$ 次操作没有办法成功，那么 $\forall y<x$ ， $y$ 次操作也一定不可能成功。
如果 $x$ 次操作可以成功，那么 $\forall z>x$ ， $z$ 次操作也一定有成功的方案。

也就是说，如果我们的答案，即合法的最少操作次数是 $m$ ，那么比 $m$ 小的操作次数一定不够，而比 $m$ 大的操作次数一定够。

我们的答案是一个分界点。我们要在答案区间 $[1,\max\{a_i\}]$ 上找一个分界点。并且我们可以通过 $O(n)$ 的一次检验来确定一个值是否可以成功。于是可以采用二分法。

假设我们的答案在区间 $[L,R]$ 上，我们取 $mid=\lfloor \frac{L+R}{2} \rfloor$ ，检验一次 $mid$ 是否可行，如果不可行，说明答案在 $[mid+1,R]$ 范围中，反之在 $[L,mid]$ 范围中，于是我们缩小了一半范围。反复做下去，只需要执行 $O(\log_2 \max(a_i))$ 次检验即可将范围缩小到 $1$ 找出答案。

图片说明

以样例为例

这样的时间复杂度降为 $O(n\log \max(a_i))$ 。

空间复杂度仍然为 $O(n)$ 。

参考代码

//c++
class Solution {
public:

    bool check(int m,vector<int>& a,int k)//验证答案的合法性
    {
        long long need=0;//用于累加计算需要的最少操作数
        for(int i=0;i<a.size();i++)
        {
            int v=a[i];
            v=max(v-m,0);
            need += ceil(v*1.0/(k-1));
        }
        return m>=need;
    }

    int dryClothes(int n, vector<int>& a, int k) {
        int max_a=0;
        for(auto &i:a)
            max_a=max(max_a,i);//取a中最大值
        if(k==1)//特判k=1的情况
            return max_a;

        int L=1,R=max_a;//二分答案
        while(L!=R)
        {
            int mid=(L+R)/2;
            if(!check(mid,a,k))
                L=mid+1;
            else
                R=mid;
        }
        return L;//最后区间长度为 1 ，就是答案。
    }
};