为了更好的阅读体检，可以查看我的算法学习博客
在线评测链接:P1297

题目描述

塔子哥安排你去他的养鸡场干活，养鸡场的名字是一串神秘代码——$Crazy4$。

塔子哥的养鸡场里养了 $N$ 只鸡（编号$1N$）。

由于塔子哥从“开封菜”引入了全自动养鸡系统，所以你要学会使用这个系统，它使用一个素质值来全方位描述每只鸡的生长情况。在这个系统里，编号为 $i$ 的鸡有一个素质值 $H_i$。

你需要操控系统给鸡补充食物，每次给某只鸡投喂食物可以使其素质值上升 $A$ ；同时由于所有的鸡都是散养的，你直接给某只鸡投喂食物，也会间接给其他所有鸡投喂食物，所以其他鸡的素质值也会同时上升 $B$ 点（ $B\le A$ ）。为了这些鸡都能够顺利成长，好及时投入市场，塔子哥希望所有的鸡的素质值都要不小于 $M$ 。

现在塔子哥想知道，在达到这个目标的前提下，最少的投喂次数是多少。

输入描述

输入第一行四个整数 $N，M，A，B$ ，分别表示鸡的数量、目标素质值、直接喂食增加的素质值、间接喂食增加的素质值。( $1\le N$,$M,A,B$ $\le 10^6$，$B\le A$ )

接下来 $N$ 行，每行一个整数 $H_i$，分别表示第 $i$ 只鸡初始的素质值 $H\_i$ 。( $0\le H_i\le 10^6$ )

输出描述

输出共一行一个整数，表示达到目标最少的喂食次数。

样例

输入

5 8 4 2
0
2
4
6
8

输出

3

样例说明

可能的一种方案为:
第一次喂食选择第1只鸡，素质变为:{4，4，6，8，10}
第二次喂食选择第1只鸡，素质变为:{8，6，8，10，12}
第三次喂食选择第1只鸡，素质变为:{12，8，10，12，14}
满足所有鸡的素质都不小于8

样例2

输入

4 10 4 4
2
2
2
2

输出

2

思路：二分答案

对于二分答案这种题目，我们先考虑如何思考得到这种解法。

首先考虑投喂次数为 $cnt$ ，那么每只鸡素质值上升 $cnt\times B$。再考虑这 $cnt$ 次投喂的每次投喂会给哪只鸡。此时每只鸡的素质为 $H_i+cnt\times B$。 当 $H_i+cnt\times B<M$，则 $cnt$ 次投喂中，需要给第 $i$ 只鸡投喂一定的次数，使得其素质 $\ge M$，这个次数为 $\lfloor \frac{M-(H_i+cnt\times B)}{A-B}\rfloor$，注意，这里的 $A>B$ 才有效，从实际意义来看，如果 $A=B$ ，则投喂给哪只鸡都是一样的，所以这里的指定投喂指的是对于 $A>B$ 的情况。

但是，当 $cnt$ 次投喂不能使得所有鸡的素质都 $\ge M$ 时，就需要提高投喂次数，但是如果说每次投喂次数 $+1$ 这样去继续判断，一次 $check$ 是 $O(n)$ 的，再加上 $O(n)$ 次投喂次数的选择，$O(n^2)$ 则必然是超时的。

当 $cnt$ 次投喂不能满足要求，那么 $cnt-1$ 次投喂必然也不能满足要求，但是 $cnt+1$ 次投喂可能会满足要求。那么这个问题就具有了二段性，存在某一个数 $mid$ ，当投喂次数大于等于 $mid$，则可以满足要求，当投喂次数小于 $mid$ ，则必然不可以满足要求。故我们二分答案，即二分投喂次数，每次 $check$ 一下是否可以满足要求即可。

时间复杂度：$O(n\log \max (h_i))$

类似题目推荐

学习教程：Codefun2000 二分答案入门教程

代码

CPP

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int n, m, A, B;
int h[1000000];
bool check(long long mid) {
    int extra = A - B;
    // mid次投喂后，每只鸡至少增加 mid*B
    long long cur = mid * B;
    for (int i = 0; i < n; ++i) {
        // ch 表示第 i 只鸡的素质还需要提升 ch 才能大于等于 M
        long long ch = m - cur - h[i];
        if (ch > 0) {
            // 注意，当 A > B 才能增加额外的素质，否则 A - B = 0，除法不能除 0
            if (A > B) {
                mid -= (ch + extra - 1) / extra;
                // 如果投喂次数超过 mid ，则说明 mid 次不够
                if (mid < 0) return false;
            } else {
                // 如果 A = B，但是这只鸡还需要增加素质，则 mid 次投喂不够
                return false;
            }
        }
    }
    // 如果所有鸡都满足条件，则返回 true
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> A >> B;

    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }

    // 二分答案，M 最多为 1e6，且最多有1e6只鸡，故最多1e12次投喂
    long long l = 0, r = 1e12;
    while (l < r) {
        long long mid = (l + r) / 2;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    cout << l << "\n";
    return 0;
}

python_152">python

python">n, m, A, B = map(int, input().split())
extra = A - B

h = [0] * n
for i in range(n):
    h[i] = int(input())


def check(mid):
    global m, B, extra
    # mid次投喂后，每只鸡至少增加 mid*B
    cur = mid * B
    i = 0
    while i < n:
        # ch 表示第 i 只鸡的素质还需要提升 ch 才能大于等于 M
        ch = m - cur - h[i]
        if ch > 0:
            # 注意，当 A > B 才能增加额外的素质，否则 A - B = 0，除法不能除 0
            if A > B:
                mid -= (ch + extra - 1) // extra
                # 如果投喂次数超过 mid ，则说明 mid 次不够
                if mid < 0:
                    return False
            else:
                # 如果 A = B，但是这只鸡还需要增加素质，则 mid 次投喂不够
                return False

        i += 1

    # 如果
    return True


# 二分答案，M 最多为 1e6，且最多有1e6只鸡，故最多1e12次投喂
l, r = 0, int(1e12)
while l < r:
    mid = (l + r) // 2
    if check(mid):
        r = mid
    else:
        l = mid + 1

print(l)

Java

java">import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int A = sc.nextInt();
        int B = sc.nextInt();
        // 读入每只鸡的素质值
        int[] h = new int[n];
        for (int i = 0; i < n; i++) {
            h[i] = sc.nextInt();
        }

        // 二分答案，M 最多为 1e6，且最多有1e6只鸡，故最多1e12次投喂
        long l = 0, r = (long) 1e12;
        while (l < r) {
            long mid = (l + r) / 2;
            if (check(mid, h, m, A, B)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }

        // 输出结果
        System.out.println(l);
    }

    // 检查是否满足条件
    public static boolean check(long mid, int[] h, int m, int A, int B) {
        int extra = A - B;
        // mid次投喂后，每只鸡至少增加 mid*B
        long cur = mid * B;
        for (int i = 0; i < h.length; ++i) {
            // ch 表示第 i 只鸡的素质还需要提升 ch 才能大于等于 M
            long ch = m - cur - h[i];
            if (ch > 0) {
                // 注意，当 A > B 才能增加额外的素质，否则 A - B = 0，除法不能除 0
                if (A > B) {
                    mid -= (ch + extra - 1) / extra;
                    if (mid < 0) return false;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
}

Go

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	in := bufio.NewReader(os.Stdin)

	var n, m, A, B int
	fmt.Fscan(in, &n, &m, &A, &B)
	// 读入每只鸡的素质值
	h := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Fscan(in, &h[i])
	}

	// 二分答案，M 最多为 1e6，且最多有1e6只鸡，故最多1e12次投喂
	var l, r int64 = 0, 1e12
	for l < r {
		mid := (l + r) / 2
		if check(mid, h, m, A, B) {
			r = mid
		} else {
			l = mid + 1
		}
	}

	// 输出结果
	fmt.Println(l)

}

// 检查是否满足条件
func check(mid int64, h []int, m, A, B int) bool {
	extra := A - B
	// mid次投喂后，每只鸡至少增加 mid*B
	cur := mid * int64(B)
	for i := 0; i < len(h); i++ {
		// ch 表示第 i 只鸡的素质还需要提升 ch 才能大于等于 M
		ch := int64(m) - cur - int64(h[i])
		if ch > 0 {
			// 注意，当 A > B 才能增加额外的素质，否则 A - B = 0，除法不能除 0
			if A > B {
				mid -= (ch + int64(extra) - 1) / int64(extra)
				if mid < 0 {
					return false
				}
			} else {
				return false
			}
		}
	}
	return true
}

Js

process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';
process.stdin.on('data', (data) => {
    input += data;
    return;
});
process.stdin.on('end', () => {
    const lines = input.trim().split('\n');

    // 读入 n，m，A，B 四个整数
    const [n, m, A, B] = lines[0].trim().split(' ').map(Number);

    // 读入每只鸡的素质值
    const h = [];
    for (let i = 0; i < n; i++) {
        h.push(parseInt(lines[i + 1]));
    }

    // 二分答案，M 最多为 1e6，且最多有1e6只鸡，故最多1e12次投喂
    let l = 0, r = 1e12;
    while (l < r) {
        const mid = Math.floor((l + r) / 2);
        if (check(mid, h, m, A, B)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }

    // 输出结果
    console.log(l);
});

// 检查是否满足条件
function check(mid, h, m, A, B) {
    const extra = A - B;
    // mid次投喂后，每只鸡至少增加 mid*B
    let cur = mid * B;
    for (let i = 0; i < h.length; i++) {
        // ch 表示第 i 只鸡的素质还需要提升 ch 才能大于等于 M
        const ch = m - cur - h[i];
        if (ch > 0) {
            // 注意，当 A > B 才能增加额外的素质，否则 A - B = 0，除法不能除 0
            if (A > B) {
                mid -= Math.ceil(ch / extra);
                if (mid < 0) {
                    return false;
                }
            } else {
                return false;
            }
        }
    }
    return true;
}

题目内容均收集自互联网，如如若此项内容侵犯了原著者的合法权益，可联系我: (CSDN网站注册用户名: 塔子哥学算法) 进行删除。