kotori的设备

题目背景

kotori 有 $n$ 个可同时使用的设备。

题目描述

第 $i$ 个设备每秒消耗 $a_i$ 个单位能量。能量的使用是连续的，也就是说能量不是某时刻突然消耗的，而是匀速消耗。也就是说，对于任意实数，在 $k$ 秒内消耗的能量均为 $k\times a_i$ 单位。在开始的时候第 $i$ 个设备里存储着 $b_i$ 个单位能量。

同时 kotori 又有一个可以给任意一个设备充电的充电宝，每秒可以给接通的设备充能 $p$ 个单位，充能也是连续的，不再赘述。你可以在任意时间给任意一个设备充能，从一个设备切换到另一个设备的时间忽略不计。

kotori 想把这些设备一起使用，直到其中有设备能量降为 $0$。所以 kotori 想知道，在充电器的作用下，她最多能将这些设备一起使用多久。

输入格式

第一行给出两个整数 $n,p$。

接下来 $n$ 行，每行表示一个设备，给出两个整数，分别是这个设备的 $a_i$ 和 $b_i$。

输出格式

如果 kotori 可以无限使用这些设备，输出 $-1$。

否则输出 kotori 在其中一个设备能量降为 $0$ 之前最多能使用多久。

设你的答案为 $a$，标准答案为 $b$，只有当 $a,b$ 满足
$\frac{|a-b|}{\max (1,b)}\le 10^{-4}$ 的时候，你能得到本测试点的满分。

样例 #1

样例输入 #1

2 1
2 2
2 1000

样例输出 #1

2.0000000000

样例 #2

样例输入 #2

1 100
1 1

样例输出 #2

-1

样例 #3

样例输入 #3

3 5
4 3
5 2
6 1

样例输出 #3

0.5000000000

提示

对于 $100\%$ 的数据，$1\le n\le 100000$，$1\le p\le 100000$，$1\le a_i,b_i\le 100000$。

题解：

#include <iostream>
using namespace std;
int n;
double p, a[100001], b[100001], sp = 0;

bool check(float x) {
    double sum = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] * x > b[i]) {
            sum += x * a[i] - b[i];
        }
    }
    return sum <= p * x;
}

double bsearch() {
    double l = 0, r = 1e10, mid;
    while (r - l > 0.000001) {
        mid = (l + r) / 2;
        if (check(mid)) {
            l = mid;
        }
        else {
            r = mid;
        }
    }
    return l;
}

int main()
{
    cin >> n >> p;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        sp += a[i];
    }
    if (sp <= p) {
        cout << -1;
    }
    else {
        cout << bsearch();
    }
    return 0;
}

思路：

这一题采用二分答案的方法来做，为什么会想到使用这个方法呢？

• 首先，题目要求的是最多能将这些设备一起使用多久，按我的理解就是，求最短时间的最大值。
• 要将所有设备一起使用，不管充电也好，不充电也罢，只要其中能量最少的设备没电了，就停止计时，现在便是求这个最少能量耗完（算上充了电）所要的时间。
• 这和二分答案的判断条件吻合，所以使用二分答案。

现在便枚举最多可以使用k秒，k的枚举范围是[0，1e10]，使左右边界逼近正确答案。只要r-l<0.000001我们就认为已经找到了正确答案，因为答案是允许误差存在的。

那么check函数该如何写呢？

• 对于每个k，我们可以计算出在这k秒内，充电宝能够给这些设备提供k*p个单位的能量。
• 由于充能是连续的，可以在设备间无缝切换的充电，所以只需要求使这些设备一起使用到k秒需要充的电的总和（当然，如果该设备本来储存有的电量就足够使用到k秒，便不需要充电了），然后将这个总和与k*p比较即可。
• 如果总和大于k*p说明充的电量不够，也就是用不了那么久，那么就应该把k调小一些，左移右边界。
• 如果总和小于k*p说明充的电量过剩了，使用时间还可以更久，就把k调大一些；如果总和刚好等于k*p，那么说明找到了一个答案，但是题目要求k的最大值，于是我们保留这个答案，继续寻找更优的解，右移左边界。

然后题目还指出了是存在无限使用的情况的，显然，这种情况只会出现充电速度极快的时候，快到供应过剩，也就是所有设备耗能的速度加起来还小于或等于充电的速度，此种情况需要特判。

-----------END------------

数列分段 Section II

题目描述

对于给定的一个长度为N的正整数数列 $A_{1\sim N}$，现要将其分成 $M$（$M\le N$）段，并要求每段连续，且每段和的最大值最小。

关于最大值最小：

例如一数列 $42451$ 要分成 $3$ 段。

将其如下分段：

$$[42][45][1]$$

第一段和为 $6$，第 $2$ 段和为 $9$，第 $3$ 段和为 $1$，和最大值为 $9$。

将其如下分段：

$$[4][24][51]$$

第一段和为 $4$，第 $2$ 段和为 $6$，第 $3$ 段和为 $6$，和最大值为 $6$。

并且无论如何分段，最大值不会小于 $6$。

所以可以得到要将数列 $42451$ 要分成 $3$ 段，每段和的最大值最小为 $6$。

输入格式

第 $1$ 行包含两个正整数 $N,M$。

第 $2$ 行包含 $N$ 个空格隔开的非负整数 $A_i$，含义如题目所述。

输出格式

一个正整数，即每段和最大值最小为多少。

样例 #1

样例输入 #1

5 3
4 2 4 5 1

样例输出 #1

6

提示

对于 $20\%$ 的数据，$N\le 10$。

对于 $40\%$ 的数据，$N\le 1000$。

对于 $100\%$ 的数据，$1\le N\le 10^5$，$M\le N$，$A_i<10^8$， 答案不超过 $10^9$。

题解：

#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
int N, M, a[100001], ans, maxa = -1;

bool check(int x) {
    int t = 1, sum = a[1];
    for (int i = 2; i <= N; i++) {
        if (sum + a[i] <= x) {
            sum += a[i];
        }
        else {
            sum = a[i];
            t++;
        }
    }
    return t <= M;
}

int bsearch() {
    int l = maxa, r = 1e9, mid;
    while (l < r) {
        mid = l + (r - l) / 2;
        if (check(mid)) {
            r = mid;
        }
        else {
            l = mid + 1;
        }
    }
    return l;
}

signed main()
{
    cin>> N >> M;
    for (int i = 1; i <= N; i++) {
        cin >> a[i];
        maxa = max(maxa, a[i]);
    }
    cout << bsearch();
    return 0;
}

思路：

这题同样是使用二分答案来做：

• 首先确定枚举的答案范围，由于Ai都是非负整数，那么最坏的情况就是最大的子段和为这堆元素中的最大值，最好的情况嘛，题目说了答案不超过1e9，就拿这个当右边界就好了。
• 然后check函数的写法，大致就是，先默认分的段数为1段，定义一个t存储数组被分成的段数，定义一个sum暂时记录当前子段的和，然后遍历A数组，每遍历到一个就判断sum+A[i]是否>=x，如果是，就sum+=A[i]，遍历下一个元素；如果不是，就说明在此处要分段了，则段数++，sum=A[i]。
• 最后判断t和M的大小，如果t大于M说明枚举的答案太小了，调大些，反之，调小一些。