CF713div3 F

你的名字 2024-03-27 16:20 78阅读 0赞

[Problem - F - Codeforces][]

题意：

小明想买一个价值为c的东西，他开始打工，他一开始在第i个职务，每天可以挣a\[i\]，他也可以用一天的时间并且花费b\[i\]升到i+1职务，第i+1职务每天可以挣a\[i+1\]

一共有n个职务，问他最少要多少天才能攒够钱c

2<=n<=2e5

思路：

注意这道题的复杂度

如果他晋升，那么晋升的那一级的状态是**确定**的

如果不晋升，那么考虑枚举在哪一级截止不晋升，复杂度O(n)级别

综上，这道题的复杂度是O(n)级别

**因此直接枚举即可！**

直接去枚举在第i级别停止一共需要多少天能攒够c

#include <bits/stdc++.h>
    #define int long long
    const int mxn=2e5+10;
    const int mxe=2e5+10;
    using namespace std;
    
    
    
    
    int n,c;
    int a[mxn],b[mxn];
    void solve(){
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        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 tot=0,pretot=0,preday=0,day=0;
        int ans=1e18;
        for(int i=1;i<=n;i++){
            tot=preday+ceil((1.0*(c-pretot))/(1.0*a[i]));//在第i天截止攒够钱的天数
            day=ceil(1.0*(b[i]-pretot)/(1.0*(a[i])));//晋升所需天数，这是确定的，是O(1)级别
            preday+=(day+1);
            pretot+=day*a[i]-b[i];
            ans=min(ans,tot);
        }
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

[Problem - F - Codeforces]: https://codeforces.com/contest/1512/problem/F

发表评论取消回复

表情：

评论列表（有 0 条评论，78人围观）

还没有评论，来说两句吧...

相关阅读

相关 CF713div3 F

[Problem - F - Codeforces][] 题意：小明想买一个价值为c的东西，他开始打工，他一开始在第i个职务，每天可以挣a\[i\]，他也可以用一天的时间

你的名字/ 2024年03月27日 16:20/ 0 赞/ 79 阅读

相关 Day 3 CF731div3 vp

这场我不好说，我感觉我是逆天，div3的C题都卡了很久，想太复杂了，一直wa2，结果没发现这么简单，越打越低能了属于是： ![2af077fd2c7a6f7e1123533c

今天药忘吃喽~/ 2024年03月27日 13:56/ 0 赞/ 64 阅读

相关【GCD可交性】CF731div3 F

好难不会感觉见过以后应该就会了吧 [Problem - F - Codeforces][] 题意：给定一个序列，每次操作可以让一个数与后面那个数取gcd，问你最少操

落日映苍穹つ/ 2024年03月27日 13:54/ 0 赞/ 67 阅读

相关 Day2 CF713 div3 vp A-G

[Dashboard - Codeforces Round \713 (Div. 3) - Codeforces][Dashboard - Codeforces Round _

深碍√TFBOYSˉ_/ 2024年03月27日 11:26/ 0 赞/ 64 阅读

相关 CF756div3 vp

又被薄纱了，rk就不放了，好丢人QwQ [Dashboard - Codeforces Round 756 (Div. 3) - Codeforces][Dashboard

た入场券/ 2024年03月26日 18:42/ 0 赞/ 65 阅读

相关【异或哈希】CF855 div3 F

感觉这道题跟之前有一题特别像，都是异或哈希感觉这种题应该很典，记录一下 [(66条消息) Codeforces Round \841 (Div. 2) and Divid

矫情吗；*/ 2024年03月26日 17:40/ 0 赞/ 102 阅读

相关【树的直径】CF863 div3 F

又是关于直径的问题感觉这个思维难度不高啊，知道它的性质大概就能想出来做法了但是我没做出来，感觉树的问题还是做的少了 [Problem - F - Codeforce

骑猪看日落/ 2024年03月22日 09:06/ 0 赞/ 76 阅读

相关（典题）线段计数 CF690 div3 F

[Problem - F - Codeforces][] 题意： ![3b4f0196ed1b4457904652cdf584dd08.png][] ![5d7f4dbb

迈不过友情╰/ 2024年03月03日 00:45/ 0 赞/ 43 阅读

相关 cf round340 div2 F（莫队）

题目链接：[传送门][Link 1] E. XOR and Favorite Number time limit per test 4 seconds mem

旧城等待，/ 2022年06月13日 02:00/ 0 赞/ 192 阅读

相关 CF572_Div2_F

题意 [http://codeforces.com/contest/1189/problem/F][http_codeforces.com_contest_1189_pr

╰半夏微凉°/ 2021年10月29日 13:32/ 0 赞/ 295 阅读