[数据结构与算法]F Financial Planning (Weekly Practice_3rd)

这个题赛时是队友搞了好久搞出来的，，，我补题一波

你需要攒够一笔钱然后退休，，，有几种投资方案，给出了每种投资方案需要的本金和每天的收入，求最短能够达到这笔钱数目的投资天数，每种投资方案只需要投一笔钱，而你可以选择多种投资方案，不必担心投资本金，你有无限的启动资金。

思路：一开始以为是背包，结果看了队友还有网上的解析之后竟然是二分，在值域上二分天数，贪心选取投资方案，其实也有背包的思想的。

做法：具体实现起来还是有很多细节需要注意。贪心体现在对于每一个天数，选择尽可能多的投资方案，使得所用天数最少而达到退休标准，感觉二分细节也体现在最后取值l和r两个边界，对于这个问题，有两种写法，下面都贴出来。

AC Code：

#include<bits/stdc++.h>

typedef long long ll;
#define INF 0x3f3f3f3f

const double PI=acos(-1);
const double eps=1e-6;
const int mod=1e9+7;
const int N=1e5+5;
int n,m;

struct node{
    int p,c;
}e[N];

int main(){
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    std::cin>>n>>m;
    for(int i=1;i<=n;i++){
        std::cin>>e[i].p>>e[i].c;
    }
    ll l=1,r=1e10,ans;
    while(l<r){
        ll now=0;
        ll mid=(l+r)/2;
        for(int i=1;i<=n;i++){
            if(e[i].p*mid-e[i].c>0){
                now+=e[i].p*mid-e[i].c;
                if(now>=m) break;
            }
        }
    if(now>=m) r=mid;
    else l=mid+1;
    }
    std::cout<<l<<'\n';
	return 0;
}

#include<bits/stdc++.h>

typedef long long ll;
#define INF 0x3f3f3f3f

const double PI=acos(-1);
const double eps=1e-6;
const int mod=1e9+7;
const int N=1e5+5;
int n,m;

struct node{
    int p,c;
}e[N];

int main(){
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    std::cin>>n>>m;
    for(int i=1;i<=n;i++){
        std::cin>>e[i].p>>e[i].c;
    }
    ll l=1,r=1e10,ans;
    while(l<=r){
        ll now=0;
        ll mid=(l+r)/2;
        for(int i=1;i<=n;i++){
            if(e[i].p*mid-e[i].c>0){
                now+=e[i].p*mid-e[i].c;
                if(now>=m) break;
            }
        }
    if(now>=m) r=mid-1,ans=mid;
    else l=mid+1;
    }
    std::cout<<ans<<'\n';
	return 0;
}

两份代码区别仅在于最后判断边界和答案取值上。二分使用很灵活，这个题也是是用了在值域上二分得到答案，给出了三秒时间，使得二分套1e5的循环不会TLE，，多做二分的题吧，还是看到应该用二分的题想不到向二分方向考虑。