杂题——第五维度

第五维度

原题

零维是点，点动成线；

一维是线，线动成面；

二维是面，面动成体；

三维是体，体动成史；

四维是史，史动????

现在人类企图理解第五维度。

而小度现在是第五维度的一位智者。一天，小度发现人类的许多科学家在试图理解第五维度，人类是四维生物，若是他们理解了第五维度，很可能也会到来第五维度的空间，这显然是小度不愿意看到的（毕竟哪里都有人口数量的问题….）所以小度希望他们尽可能晚的理解第五维度，因此，小度用更高维度的视角把所有人类中在理解第五维的科学家都看到了，而这些科学家的智商会不一样，所以他们的理解速度 Vi 也会不一样；并且，他们开始理解的时间点 Si 也不一样。理解速度 Vi 描述为每过单位时间可获得 Vi 个单位理解力，也就是说在 +1Si+1 的时间点该科学家会第一次贡献 Vi 的理解力。我们定义理解力总数超过 m 时理解了第五维度。 小度因为维度更高，可以使用时间悖论来给人类一次重大的打击，小度可以让任意一位科学家在任意一个时间点消失，所以他接下来的理解不会继续；而且人类不会记得他，所以他之前的贡献会消失。因为小度能力有限，所以小度只能使用一次暂时悖论。

现在求在尽可能晚的情况下，人类理解第五维度的最早时间点。

时间点初始为00，但显然，没有科学家能够在 00 时刻有贡献。

格式

输入格式：

第一行给出一个整数 n 和一个整数 m ，表示有 n 个科学家，在理解力总数超过 m 时理解了第五维度；
第二至 n+1 行：每行两个整数 Si​ 和 Vi​；
对于 100% 的数据：1≤n≤105，1≤m≤2∗109；
对于 100% 的数据：0≤Si​≤2∗109，0≤Vi​≤103。

输出格式：

一行，包含一个整数 T 表示在尽可能晚的情况下，人类理解第五维度的最早时间点。
若是人类永远无法理解第五维度，则输出-1。

样例 1

输入：

1
2
3
4
3 10
0 1
4 6
5 1

输出：

1
8
样例 2

输入：

1
2
3
4
3 10
0 0
4 0
5 1

复制

输出：

1
-1
备注
1
2
对于第一个样例，使得 S i=4 , V i=6 该科学家消失，则每个时刻总共理解力为：0 1 2 3 4 5 7 9 11 ，在时刻 8 超过 m=10 ，因此输出8。
对于第二个样例，人类永远无法理解第五维度，因此输出 −1 。

思路

​ 看代码即可。

代码（二分 + 贪心）

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
#include<bits/stdc++.h> 

using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, m;
LL v[N], w[N];


bool check(LL t) {
    LL sum = 0, maxn = 0;
    for (int i = 1; i <= n; i++) {
        if (t <= v[i]) continue; 
        sum += (t - v[i]) * w[i];
        maxn = max(maxn, (t - v[i]) * w[i]);
    }
    return sum - maxn > m;
}
int main( )
{
    // 设任意一个时间t为人类最晚理解时间，那么每位科学家对其贡献为(t - v[i]) * w[i];
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n >> m;

    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    LL l = 0, r = 2e11;
    while (l < r) {
        LL mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }     
    if (check(r)) cout << r;
    else cout << "-1";
    return 0;
}