东莞个人免费建网站,电子商务网站建设实训需求分析,seo做的比较好的网站,长安网站建设推广公司一、贪心算法的思想 贪心算法是一种求解问题时#xff0c;总是做出在当前看来是最好的选择#xff0c;不从整体最优上加以考虑的算法。 二.用贪心算法的解题策略 其基本思路是从问题的某一个初始解出发一步一步地进行#xff0c;根据某个优化测度#xff0c;每一步都要确保…一、贪心算法的思想 贪心算法是一种求解问题时总是做出在当前看来是最好的选择不从整体最优上加以考虑的算法。 二.用贪心算法的解题策略 其基本思路是从问题的某一个初始解出发一步一步地进行根据某个优化测度每一步都要确保能获得局部最优解。贪心算法的关键在于贪心策略的选择而不是对所有问题都能得到整体最优解。若下一个数据和部分最优解连在一起不再是可行解时就不把该数据添加到部分解中直到把所有数据枚举完或者不能再添加算法停止。” 三典型题 第五维度
零维是点点动成线
一维是线线动成面
二维是面面动成体
三维是体体动成史
四维是史史动????
现在人类企图理解第五维度。
而小度现在是第五维度的一位智者。一天小度发现人类的许多科学家在试图理解第五维度人类是四维生物若是他们理解了第五维度很可能也会到来第五维度的空间这显然是小度不愿意看到的毕竟哪里都有人口数量的问题….所以小度希望他们尽可能晚的理解第五维度因此小度用更高维度的视角把所有人类中在理解第五维的科学家都看到了而这些科学家的智商会不一样所以他们的理解速度 Vi 也会不一样并且他们开始理解的时间点 Si 也不一样。理解速度 Vi 描述为每过单位时间可获得 Vi 个单位理解力也就是说在 Si1 的时间点该科学家会第一次贡献 Vi 的理解力。我们定义理解力总数超过m 时理解了第五维度。 小度因为维度更高可以使用时间悖论来给人类一次重大的打击小度可以让任意一位科学家在任意一个时间点消失所以他接下来的理解不会继续而且人类不会记得他所以他之前的贡献会消失。因为小度能力有限所以小度只能使用一次暂时悖论。
现在求在尽可能晚的情况下人类理解第五维度的最早时间点。
时间点初始为00但显然没有科学家能够在 00 时刻有贡献。
格式 输入格式 第一行给出一个整数 n 和一个整数 m 表示有 n 个科学家在理解力总数超过 m 时理解了第五维度 第二至 n1 行每行两个整数Si 和 Vi 对于 100% 的数据1≤n≤10^5m≤2∗10^9 对于 100% 的数据00≤Si≤2∗10^90≤Vi≤10^3。 输出格式 一行包含一个整数 T 表示在尽可能晚的情况下人类理解第五维度的最早时间点。 若是人类永远无法理解第五维度则输出-1。 题解 #includebits/stdc.h using namespace std;
long long s[100000],v[100000],n,m;
bool check(int t){long long sum0,maxn-1;for(int i1;in;i){if(t-s[i]0) continue;sum(t-s[i])*v[i];maxnmax(maxn,(t-s[i])*v[i]);}return sum-maxnm;
}
int main( )
{cinnm;for(int i1;in;i){cins[i]v[i];}int l0,r999999999;while(lr){int mid(lr)/2;if(check(mid)) rmid;else lmid1;}if(check(1)) coutl;else cout-1;return 0;
}
执行结果
