贪心算法的思路和典型例题

一、贪心算法的思想

二.用贪心算法的解题策略

三典型题 

第五维度

零维是点，点动成线；

一维是线，线动成面；

二维是面，面动成体；

三维是体，体动成史；

四维是史，史动????

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

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

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

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

格式

题解

 

#include<bits/stdc++.h> 

using namespace std;
long long s[100000],v[100000],n,m;
bool check(int t){
    long long sum=0,maxn=-1;
    for(int i=1;i<=n;i++){
        if(t-s[i]<=0) continue;
        sum+=(t-s[i])*v[i];
        maxn=max(maxn,(t-s[i])*v[i]);
    }
    return sum-maxn>m;
}
int main( )
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>s[i]>>v[i];
    }
    int l=0,r=999999999;
    while(l<r){
        int mid=(l+r)/2;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    if(check(1)) cout<<l;
    else cout<<-1;
    return 0;
}

执行结果：