[COCI2008-2009#2] SVADA 解题记录

Autream · 2024-03-03 20:20:23 · 题解

题意简述

有两种猴子，第一种会摘椰子，第二种会开椰子。

摘椰子的猴子有 n 只，需要先用 a_i 秒找椰子，再用 b_i 秒摘椰子。

开椰子的猴子有 m 只，需要先用 c_i 秒找工具，再用 d_i 秒开椰子。

现给你一个正整数 t，为摘椰子的猴子与开椰子的猴子所用的时间和，求在什么时候开的椰子数量等于摘的椰子的数量。

题目分析

首先观察数据范围：1 \leq t \leq 1 \times 10^9，枚举不行，考虑二分答案。

枚举“开的椰子数量等于摘的椰子的数量”的时刻 x。

直接模拟过程，最后判断开的椰子和摘的椰子大小关系即可。

bool check(int x){
    int cnt1=0,cnt2=0;
    for(int i=1;i<=n;i++){//n只猴子同时进行，记录每只猴子开的数量
        if(x>=a[i]){
            cnt1+=(x-a[i])/b[i]+1;//使用a[i]的时间找椰子，剩余(x-a[i])的时间每b[i]秒开一个
        }
    }
    for(int i=1;i<=m;i++){
        if(t>=x+c[i]){//摘椰子用了x秒
            cnt2+=(t-x-c[i])/d[i]+1;//使用c[i]的时间找工具，剩余(t-x-c[i])的时间每d[i]秒开一个
        }
    }
    return cnt1-cnt2>0;//摘的椰子>开的椰子
}