CF713div3 F

你的名字 2024-03-27 16:20 25阅读 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 条评论，25人围观）

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

相关阅读

相关 CF713div3 F

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

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

相关【bitmask】CF731div3 D

这道题赛后秒了，是个结论（感觉也不算，因为非常好推）感觉这种序列+bitmask就是把这个序列想象成一个01矩阵，横向是30位的bit，纵向是n个数，这样感觉会好想一点，如

谁践踏了优雅/ 2024年03月27日 13:53/ 0 赞/ 14 阅读

相关 CF790 div4 F(双指针） H（逆序对）

乐，被div4薄纱了没想到把所有出现次数>=k的数放一个数组里然后双指针还有H，连逆序对都没看出来，嘻感觉以后还是写写div4算了，写什么div2啊，caibi

- 日理万妓/ 2024年03月27日 10:24/ 0 赞/ 14 阅读

相关 20230304 CF855 div3 vp

[Dashboard - Codeforces Round 855 (Div. 3) - Codeforces][Dashboard - Codeforces Round 85

比眉伴天荒/ 2024年03月26日 17:41/ 0 赞/ 14 阅读

相关【异或哈希】CF855 div3 F

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

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

相关【树的直径】CF863 div3 F

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

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

相关 Codeforces Round 895 (Div. 3)F

[Problem - F - Codeforces][] F. Selling a Menagerie 由题意知，一个动物如果其害怕的动物还没有被买出，就可以卖出翻倍的

短命女/ 2024年03月08日 08:42/ 0 赞/ 30 阅读

相关 cf round340 div2 F（莫队）

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

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

相关 sorting, two pointers(cf div.3 1113)

![1613216-20190312232041133-1561419799.png][] 注意题目条件：a balanced team, 仅保证大家水平差距不超过5即可，不

绝地灬酷狼/ 2021年12月23日 16:39/ 0 赞/ 116 阅读

相关 CF572_Div2_F

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

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