P3743. kotori的设备

发表于 分类于 阅读次数： Waline： 本文字数： 1.1k 阅读时长 ≈ 4 分钟

考点

  • 二分
  • 贪心

题解

见思路

思路

二分

题目给了误差范围1e-4，显然就是让我们进行实数二分

把所有设备的耗电速度加起来，将其视作一个更大的设备；如果充电速度大于等于大设备的耗电速度，显然时间可以无限续，输出-1

二分设备使用时间x，左端点为0，右端点为1e15（由于充电的存在，右端点不确定，取大点总没错）

我们并不关心充电器具体到哪个设备充了多少的电，因为充电过程是连续的，充电的总电量总是x * P

故而可从充电的总电量，维持各设备的电量大于等于0的总需电量，进行单调性判断

因为我们需要让所有设备运行x时间呐！电量在这期间肯定大于等于0

遍历设备，判断当前设备的耗电量cost = arr[i].a_ * x是否大于存量arr[i].b_，大于说明还需要充cost - arr[i].b_的电量

若当前耗电量小于等于存量，说明不需要充电

最后判断单调性：

  • 充电的总电量大于维持各设备的电量大于等于0的总需电量，说明设备使用时间x选小了，应该向右端点移动
  • 若等于，也要向右移动（求最大）
  • 若小于，说明设备使用时间x选大了，应该向左端点移动
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>

using namespace std;

const double eps = 1e-4;

const int LEN = 1e5 + 50;

int N, P;

struct Node
{
    int a_, b_;
} arr[LEN];

bool check(double x)
{
    double sum = 0, cost;
    for (int i = 0; i < N; ++i)
    {
        if ((cost = arr[i].a_ * x) > arr[i].b_)
            sum += cost - arr[i].b_;
    }
    return sum <= x * P;
}

int main()
{
    cin >> N >> P;
    double sum = 0;
    for (int i = 0; i < N; ++i)
    {
        cin >> arr[i].a_ >> arr[i].b_;
        sum += arr[i].a_;
    }
    if (sum <= P)
    {
        cout << "-1";
        return 0;
    }
    double l = 0, r = 1e15;
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid))
            l = mid;
        else
            r = mid;
    }
    cout << r;
    return 0;
}

贪心

这道题第一眼我就认为应该用贪心写更好.....

设消耗比t等于耗电速度a除以电量b，显然t越大电量越快到零，也是最需要充电的；按照下面这个优先级进行排序 \[ i<j, \frac{a_i}{b_i}>\frac{a_j}{b_j}\rightarrow a_i\cdot b_j>b_i\cdot a_j \\ \] 每次将当前消耗比最大ti与次大tj的两个设备作比较：

  • 若ti的充电工作时间，等于tj的不充电工作时间，就将它俩合并

  • 若ti的充电工作时间仍小于tj的不充电工作时间，则两者无法合并；直接输出ti的充电工作时间并退出 \[ \underset{\text{耗电量}}{\underbrace{\frac{b_j}{a_j}\cdot a_i}}>\underset{\text{电量}+\text{充电量}}{\underbrace{b_i+P\cdot \frac{b_j}{a_j}}} \]

具体解释一下合并的含义，设ti的不充电工作时间为Ta，tj的不充电工作时间为Tb，显然Ta < Tb

如果能靠充电，让ti多Tb - Ta的工作时间，即ti的充电工作时间等于tj的不充电工作时间

那么Tb前，充电器只给ti充电；Tb后，充电器要来回给ti和tj一起充电，保证它们俩尽可能地工作时间长

为什么可以来回？因为充电器是瞬移的

所以原来的充电效率是P，现在相同时间要给两个设备充电，效率只能减半为P/2

你肯定会问，那也不能一直P / 2、P / 3、P / 4...除下去呀！精度肯定不准！

故而将两者合并，耗电速度相加，电量也相加，视作一个大设备整体进行充电就行啦！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>

using namespace std;

const int LEN = 1e5 + 50;

int N, P;

struct Node
{
    double a_, b_;
} arr[LEN];

int main()
{
    cin >> N >> P;
    double sum = 0;
    for (int i = 0; i < N; ++i)
    {
        cin >> arr[i].a_ >> arr[i].b_;
        sum += arr[i].a_;
    }
    if (sum <= P)
    {
        cout << "-1";
        return 0;
    }
    sort(arr, arr + N, [](Node &a, Node &b) -> bool
         { return a.a_ * b.b_ > a.b_ * b.a_; });
    for (int i = 0; i < N - 1; ++i)
    {
        if (arr[i + 1].b_ * arr[i].a_ > arr[i + 1].a_ * arr[i].b_ + P * arr[i + 1].b_)
        {
            cout << arr[i].b_ / (arr[i].a_ - P);
            return 0;
        }
        arr[i + 1].a_ += arr[i].a_;
        arr[i + 1].b_ += arr[i].b_;
    }
    cout << arr[N - 1].b_ / (arr[N - 1].a_ - P);
    return 0;
}