百度之星-第五维度

题目：第五维度

零维是点，点动成线；

一维是线，线动成面；

二维是面，面动成体；

三维是体，体动成史；

四维是史，史动????

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

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

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

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

思路：

正着做的话，很容易想到模拟，但是“消失一个人”会对之前的结果产生影响，所以不太好做。
我们可以倒着从结果推：还是二分答案，那么这次二分什么呢？当然是时间了！

我们只要遍历每个二分后的时间点就行，看在有效时间内贡献最多的人消失后还能不能理解第五维度，如果仍然可以理解，那么我们就继续减少时间，直到不能再减少时间，那么答案就出来了。

那么怎么知道最终的二分结果究竟能不能使人理解理解第五维度呢？我们只需要再带入一次check函数判断即可！好了，下面就是代码部分（依然有注解哦~）

#include <bits/stdc++.h>//第五维度：有n个科学家，在不同的时间点s出现，之后每天贡献v，当人类贡献总和大于m时，就理解了第五维度，但上帝可以随机 using namespace std; //使一个人消失，他的所有贡献也会消失，问人类最晚多久可以理解第五维度，如果不能输出-1 typedef long long ll; ll s[100000],v[100000],n,m; bool check(ll t){ ll sum=0,max_=-1; for(int i=1;i<=n;i++){ if(t<=s[i])continue;//后面出现的人就跳过 sum+=(t-s[i])*v[i]; max_=max(max_,(t-s[i])*v[i]);//找最大贡献的人 } return sum-max_>m; } int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ scanf("%d %d",&s[i],&v[i]); } ll mid,l=0,r=2e9; while(l<=r){ mid=(l+r)>>1; if(check(mid)) r=mid-1; else l=mid+1; } if(check(l))cout<<l;//对二分查找失败的情况进行特判 else cout<<-1; }

怎么样，今天的题是不是很简单~