F. Education

考虑贪心
显然我们每次只有这样一种情况 就是钱够了就升级 然后到一个位置就一直不动了
不可能我们先在一个位置钱赚够了 再赚几轮 再去下一级
那么证明我们知道下一级赚的更多 我们还要在这个少的赚几轮 不是春春脑瘫吗
所以我们枚举在每一个位置速通前面的 再在这个位置狂赚
时间复杂度是O（n）的
注意的就是now更新时是now=now+up(need,a[i])*a[i]-b[i]
对于我们需要的上取整天数 再减去原本要的钱-b[i]

void solve(){
    int n,c;cin>>n>>c;
    vector<int>a(n+10),b(n+10);
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<n;i++)cin>>b[i];
    int now=0,day=0,ans=up(c,a[1]);
    for(int i=1;i<n;i++){
        int need=b[i]-now;
        if(need<=0){
            now-=b[i];
            day++;
        }else{
            day+=up(need,a[i])+1;
            now=now+up(need,a[i])*a[i]-b[i];
        }
        ans=min(ans,day+up(c-now,a[i+1]));
    }
    cout<<ans<<endl;
}

原文地址：http://www.cnblogs.com/ycllz/p/16865586.html