Codeforces1512 F. Education（贪心）

题意：

解法：

从左到右枚举最后从哪一个a[i]一直干到c块钱.由于a[]是递增的,那么肯定越早到达i位置越好,
那么计算出到达i需要的最小天数,计算a[i]干到c块钱的天数更新答案即可.复杂度O(n).

code：

#include
#define int long long
using namespace std;
const int maxm=2e6+5;
int a[maxm];
int b[maxm];
int n,c;
void solve(){cin>>n>>c;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n-1;i++){cin>>b[i];}int ans=1e18;int day=0;int now=0;for(int i=1;i<=n;i++){//利用a[i]到达c需要的天数int rem=c-now;int need=rem/a[i]+(rem%a[i]!=0);ans=min(ans,day+need);if(i<=n-1){//转到a[i+1]if(now>=b[i]){now-=b[i];}else{int rem=b[i]-now;int need=rem/a[i]+(rem%a[i]!=0);day+=need;now+=need*a[i];now-=b[i];}day++;//转移需要一天}}cout<<ans<<endl;
}
signed main(){ios::sync_with_stdio(0);int T=1;cin>>T;while(T--){solve();}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！