信息奥赛题单｜二分答案

二分答案

题单 🧑🏻‍💻

题目来源	题目名称	题目链接	备注	难度
CodeForces - 1873E	Building an Aquarium	链接🔗	二分答案	🟢
OpenJudge NOI 1.11.06	月度开销	链接🔗	整数二分 + 二分答案	🟡
OpenJudge NOI 1.11.04	网线主管	链接🔗	浮点数二分 + 二分答案	🟡

---

题解 🚀

Building an Aquarium

题目信息 📚

【题目名称】CodeForces - 1873E - Building an Aquarium

【题目描述】

You love fish, that’s why you have decided to build an aquarium. You have a piece of coral made of $n$ columns, the $𝑖$-th of which is $a_i$ units tall. Afterwards, you will build a tank around the coral as follows:

• Pick an integer $h \ge 1$ — the height of the tank. Build walls of height $h$ on either side of the tank.
• Then, fill the tank up with water so that the height of each column is $h$, unless the coral is taller than $h$; then no water should be added to this column.

For example, with $a=[3,1,2,4,6,2,5]$ and a height of $h=4$, you will end up using a total of $𝑤=8$ units of water, as shown.

You can use at most $𝑥$ units of water to fill up the tank, but you want to build the biggest tank possible. What is the largest value of ℎℎ you can select?

【输入】

The first line contains a single integer $t(1 \le t \le 10^4)$ — the number of test cases.

The first line of each test case contains two positive integers $n$ and $x$ $(1 \le n \le 2*10^5,1 \le 𝑥 \le 10^9)$— the number of columns of the coral and the maximum amount of water you can use.

The second line of each test case contains $n$ space-separated integers $a_i$ $(1 \le a_i \le 10^9)$— the heights of the coral.

The sum of $n$ over all test cases doesn’t exceed $2*10^5$.

【输出】

For each test case, output a single positive integer $h(h \ge 1)$ — the maximum height the tank can have, so you need at most $x$ units of water to fill up the tank.

We have a proof that under these constraints, such a value of $h$ always exists.

【输入样例】

5
7 9
3 1 2 4 6 2 5
3 10
1 1 1
4 1
1 4 3 4
6 1984
2 6 5 9 1 8
1 1000000000
1

【输出样例】

4
4
2
335
1000000001

【提示】

The first test case is pictured in the statement. With $h=4$ we need $8$ units of water, but if $ℎ$ is increased to $5$ we need $13$ units of water, which is more than $x=9$. So $h=4$ is optimal.

In the second test case, we can pick $h=4$ and add $3$ units to each column, using a total of $9$ units of water. It can be shown that this is optimal.

In the third test case, we can pick $h=2$ and use all of our water, so it is optimal.

【题目链接】

https://codeforces.com/problemset/problem/1873/E

---

题目解析 🍉

【题目分析】

二分答案

【 C++ 代码】

#include<bits/stdc++.h>
 
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
LL n, x;
LL a[N];
 
// 判断当前水缸高度t能否被满足
bool check(int t) {
    LL sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += max(t - a[i], 0LL);
    }
    return sum <= x;
}
 
void solve() {
    cin >> n >> x;
    for (int i = 1; i <= n; i++) cin >> a[i];
 
    LL l = 1, r = 2e9 + 10;
    while (l < r) {
        LL mid = l + r + 1 >> 1;
        if (check(mid))
            l = mid;
        else
            r = mid - 1;
    }
    cout << l << endl;
}
 
int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);
 
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
 
    return 0;
}

---

月度开销

题目信息 📚

【题目名称】OpenJudge NOI 1.11.04 - 月度开销

【题目描述】

杰哥不仅是一名学霸还是一名农场主，大家都亲切的叫他 Farmer Jie，简称 FJ。经营农场是一个非常很花钱的事情。

在将来的 $N$ 天($1 \le N \le 100000$) 中 FJ 每天需要花 $a_i$ 的钱($1 \le ai \le 10,000$)。现在他想把这些天分成M份（每份都是一天或连续的几天），每份的总花费为该份所有天的花费之和，要求如何划分使得 $M$ 份中最大总花费尽量小。

FJ 很懒，所以他向聪明的程序员——你来求助。请帮他算出最优的划分方式，并将其中的最大花费输出。

【输入】

该题包含多组样例。

第 $1$ 行：两个用空格隔开的整数：$N$ 和 $M$

第 $2$～$N+1$ 行：每行包含一个整数 $a_i$ 表示 FJ 在第 $i$ 天的花费。

【输出】

输出最小的最大花费。

【输入样例】

7 5
100
400
300
100
500
101
400

【输出样例】

500

【题目链接】

http://noi.openjudge.cn/ch0111/06/

---

题目解析 🍉

【题目分析】

二分答案 + check函数编写

【 C++ 代码】

#include<bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10;

int n, m;
int a[N]; // 存储每个月的开销

// 核心思路：如果当前最大值为cost，按照顺序依次合并，合并后的数量是否 <= m
bool check(int cost) {
    int i = 1, cnt = 0;  // 函数内的cnt记得初始化
    int sum = 0;  // 记录当前合并块的开销和，每次都需要将其与cost比较

    // 从第一个月份开始，一个一个合并，统计<=cost的块数
    // 且由于设定左边界时，l为a中单个的最大值，所以其他月份至少能单独成1块
    while (i <= n) {
        sum = sum + a[i];
        if (sum > cost) {  // 说明当前的a[i]无法加入此块
            cnt++;
            sum = a[i];
        }
        i++;
    }
    if (sum > 0) cnt++;
    if (cnt <= m) {
//        cout << "cost " << cost << " cnt " << cnt << endl;
        return true;
    } else return false;

}

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    // 多组样例
    while (cin >> n >> m) {
        // 读入每月开销和划分块数
        for (int i = 1; i <= n; i++) cin >> a[i];

        // 设定二分边界（如何设定二分边界，是理解此题重要的第一步）
        int maxV = a[1], sum = a[1];
        for (int i = 2; i <= n; i++) {
            sum += a[i];
            if (a[i] > maxV) maxV = a[i];
        }
        // 左边界为单独月份的最大值，右边界为所有月份最大值
        int l = maxV, r = sum;  // 这里为了逻辑清晰，牺牲了代码简洁性

        // 二分模版
        while (l < r) {
            int mid = l + r >> 1;
            // 书写check函数，判断当前设定答案mid，是否能够满足要求，是解出本题的关键，
            // 核心思路：如果当前最大值为cost，按照顺序依次合并，合并后的数量 <= m，说明mid可以满足，否则不能满足
            // 上面的核心思路一开始不理解没关系，过程详见check函数
            if (check(mid)) r = mid;  // 当前mid满足，令r=mid，寻找更小值，看看是否满足
            else l = mid + 1;
        }

        // 输出二分结果
        cout << l << endl;
    }

    return 0;
}

---

网线主管

题目信息 📚

【题目名称】网线主管

【题目描述】

仙境的居民们决定举办一场程序设计区域赛。裁判委员会完全由自愿组成，他们承诺要组织一次史上最公正的比赛。他们决定将选手的电脑用星形拓扑结构连接在一起，即将它们全部连到一个单一的中心服务器。为了组织这个完全公正的比赛，裁判委员会主席提出要将所有选手的电脑等距离地围绕在服务器周围放置。

为购买网线，裁判委员会联系了当地的一个网络解决方案提供商，要求能够提供一定数量的等长网线。裁判委员会希望网线越长越好，这样选手们之间的距离可以尽可能远一些。

该公司的网线主管承接了这个任务。他知道库存中每条网线的长度（精确到厘米），并且只要告诉他所需的网线长度（精确到厘米），他都能够完成对网线的切割工作。但是，这次，所需的网线长度并不知道，这让网线主管不知所措。

你需要编写一个程序，帮助网线主管确定一个最长的网线长度，并且按此长度对库存中的网线进行切割，能够得到指定数量的网线。

【输入】

第一行包含两个整数 $N$ 和 $K$，以单个空格隔开。$N(1 \le N \le 10000)$是库存中的网线数，$K(1 \le K \le 10000)$ 是需要的网线数量。

接下来 $N$ 行，每行一个数，为库存中每条网线的长度（单位：米）。

所有网线的长度至少 $1$m，至多 $100$ km。输入中的所有长度都精确到厘米，即保留到小数点后两位。

【输出】

网线主管能够从库存的网线中切出指定数量的网线的最长长度（单位：米）。必须精确到厘米，即保留到小数点后两位。

若无法得到长度至少为 $1$ cm的指定数量的网线，则必须输出 “0.00”（不包含引号）。

【输入样例】

4 11
8.02
7.43
4.57
5.39

【输出样例】

2.00

【题目链接】

http://noi.openjudge.cn/ch0111/04/

---

题目解析 🍉

【题目分析】

刚开始用浮点数二分，一直有测试点过不去。

网上搜索后，发现这题浮点数二分时，精度不够，故转换成整数二分。

转换成整数二分时，有两个点需要注意

• check 函数中的 cnt 变量有可能爆 int ，需要改成 long long ，否则最后一个测试点无法通过
• 在将「浮点数 → 整数」的过程中，需要使用 round() 函数，四舍五入提高精度

【 C++ 代码】

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 1e5 + 10;
int n, m, a[N];
double x;

// 判断对于当前长度x，库存电线切割后的数量是否 >= m
bool check(int x) {
    LL cnt = 0;  // 注意，这里cnt可能爆int，需要使用LL（否则最后一个测试点过不去）
    for (int i = 1; i <= n; i++) cnt += a[i] / x;
    return cnt >= m;
}

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    // 读入数据，并且将浮点数转换成整数
    cin >> n >> m;
    // round函数作用是四舍五入
    for (int i = 1; i <= n; i++) cin >> x, a[i] = round(x * 100.0);

    // 判断该问题是否有解
    if (!check(1)) cout << "0.00" << endl;
    else {
        // 确定二分左右边界
        int *it = max_element(a + 1, a + n + 1);
        int l = 1, r = *it;

        // 二分模版
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (check(mid)) l = mid;
            else r = mid - 1;
        }

        cout << fixed << setprecision(2) << l / 100.0 << endl;
    }

    return 0;
}

---