P16425 「YLLOI-R4-T1」珊瑚海Link: https://www.luogu.com.cn/problem/P16425题目描述小 Y 很懒他想让小 Z 帮他接水。小 Z 每次接水有三种方案只给小 Y 接一杯。只给自己接一杯。给小 Y 和自己各接一杯。接一次水消耗的体力为接水杯数与路程d dd的和。小 Z 现在要使用m mm点体力给小 Y 接n nn杯水他想知道在给小 Y 接水杯数足够的基础上他最多能给自己接多少杯水。若无法给小 Y 接足够的水则输出-1。输入格式一行三个整数n , m , d n,m,dn,m,d。输出格式一个整数表示答案。输入输出样例 #1输入 #13 10 2输出 #11输入输出样例 #2输入 #22 10 1输出 #24输入输出样例 #3输入 #32 9 4输出 #3-1说明/提示【样例解释#1】一种可能的方案小 Z 一共接3 33次水前2 22次只给小 Y 接一杯耗费2 × ( d 1 ) 6 2\times(d1)62×(d1)6点体力第3 33次给小 Y 和自己各接一杯耗费d 2 4 d24d24点体力。一共耗费10 1010点体力给自己接了1 11杯水给小 Y 接了3 33杯水。可以证明在保证耗费体力不超过10 1010且给小 Y 接的水杯数恰好为3 33的情况下他最多只能给自己接1 11杯水。【数据范围】本题采用捆绑测试。Subtask 120 ptsd 0 d0d0。Subtask 220 ptsn 0 n0n0。Subtask 320 ptsm 0 m0m0。Subtask 420 ptsn , m , d ≤ 100 n,m,d\le 100n,m,d≤100。Subtask 520 pts无特殊限制。对于全部数据保证0 ≤ n , m , d ≤ 10 9 0\le n,m,d\le 10^90≤n,m,d≤109。Solution1. 题意小 Z 帮小 Y 接水。小 Z 每次接水有三种方案方案消耗体力Y 获得杯数Z 获得杯数1 11d 1 d1d11 110 002 22d 2 d2d21 111 113 33d 1 d1d10 001 11小 Z 现在要使用m mm点体力给小 Y 接n nn杯水求给小 Y 接水杯数足够的基础上他最多能给自己接多少杯水。2. 分析很容易发现方案2 22“减去”方案1 11等于“只消耗1 11的体力为自己带来一杯水”能节约d dd的能量。因此贪心思路非常明确先用n ( d 1 ) n(d1)n(d1)的基础值去试探能不能达成保底够不到就是− 1 -1−1。这个计划目前处于拟执行状态包含n nn次方案1 11的执行。在上面拟执行的计划上只要体力足够就不断用方案2 22替换方案1 11直到剩余体力不够或者方案1 11全部被取缔。如果这之后体力还有剩余就采用方案3 33为 Z 单独接水。每次消耗d 1 d1d1体力换1 11杯水。照着这个思路直接就得到答案。A { − 1 , m n ( d 1 ) m − n ( d 1 ) , n ( d 1 ) ≤ m ≤ n ( d 2 ) ⌊ m − n d 1 ⌋ , m n ( d 2 ) A \begin{cases} -1, m n(d1) \\ m - n(d1), n(d1) \le m \le n(d2) \\ \left\lfloor \dfrac{m-n}{d1} \right\rfloor, m n(d2) \end{cases}A⎩⎨⎧−1,m−n(d1),⌊d1m−n⌋,mn(d1)n(d1)≤m≤n(d2)mn(d2)时间复杂度和空间复杂度皆为O ( 1 ) O(1)O(1)。3. 代码usingSystem;classT663578{longn,m,d;publicstaticvoidMain(){varinputConsole.ReadLine().Split();nConvert.ToInt64(input[0]);mConvert.ToInt64(input[1]);dConvert.ToInt64(input[2]);longmin_costn*(d1);if(mmin_cost){Console.Write(-1);}elseif(mn*(d2)){Console.Write(m-min_cost);}else{Console.Write((m-n)/(d1));}}}
P16425 「YLLOI-R4-T1」珊瑚海 题解
P16425 「YLLOI-R4-T1」珊瑚海Link: https://www.luogu.com.cn/problem/P16425题目描述小 Y 很懒他想让小 Z 帮他接水。小 Z 每次接水有三种方案只给小 Y 接一杯。只给自己接一杯。给小 Y 和自己各接一杯。接一次水消耗的体力为接水杯数与路程d dd的和。小 Z 现在要使用m mm点体力给小 Y 接n nn杯水他想知道在给小 Y 接水杯数足够的基础上他最多能给自己接多少杯水。若无法给小 Y 接足够的水则输出-1。输入格式一行三个整数n , m , d n,m,dn,m,d。输出格式一个整数表示答案。输入输出样例 #1输入 #13 10 2输出 #11输入输出样例 #2输入 #22 10 1输出 #24输入输出样例 #3输入 #32 9 4输出 #3-1说明/提示【样例解释#1】一种可能的方案小 Z 一共接3 33次水前2 22次只给小 Y 接一杯耗费2 × ( d 1 ) 6 2\times(d1)62×(d1)6点体力第3 33次给小 Y 和自己各接一杯耗费d 2 4 d24d24点体力。一共耗费10 1010点体力给自己接了1 11杯水给小 Y 接了3 33杯水。可以证明在保证耗费体力不超过10 1010且给小 Y 接的水杯数恰好为3 33的情况下他最多只能给自己接1 11杯水。【数据范围】本题采用捆绑测试。Subtask 120 ptsd 0 d0d0。Subtask 220 ptsn 0 n0n0。Subtask 320 ptsm 0 m0m0。Subtask 420 ptsn , m , d ≤ 100 n,m,d\le 100n,m,d≤100。Subtask 520 pts无特殊限制。对于全部数据保证0 ≤ n , m , d ≤ 10 9 0\le n,m,d\le 10^90≤n,m,d≤109。Solution1. 题意小 Z 帮小 Y 接水。小 Z 每次接水有三种方案方案消耗体力Y 获得杯数Z 获得杯数1 11d 1 d1d11 110 002 22d 2 d2d21 111 113 33d 1 d1d10 001 11小 Z 现在要使用m mm点体力给小 Y 接n nn杯水求给小 Y 接水杯数足够的基础上他最多能给自己接多少杯水。2. 分析很容易发现方案2 22“减去”方案1 11等于“只消耗1 11的体力为自己带来一杯水”能节约d dd的能量。因此贪心思路非常明确先用n ( d 1 ) n(d1)n(d1)的基础值去试探能不能达成保底够不到就是− 1 -1−1。这个计划目前处于拟执行状态包含n nn次方案1 11的执行。在上面拟执行的计划上只要体力足够就不断用方案2 22替换方案1 11直到剩余体力不够或者方案1 11全部被取缔。如果这之后体力还有剩余就采用方案3 33为 Z 单独接水。每次消耗d 1 d1d1体力换1 11杯水。照着这个思路直接就得到答案。A { − 1 , m n ( d 1 ) m − n ( d 1 ) , n ( d 1 ) ≤ m ≤ n ( d 2 ) ⌊ m − n d 1 ⌋ , m n ( d 2 ) A \begin{cases} -1, m n(d1) \\ m - n(d1), n(d1) \le m \le n(d2) \\ \left\lfloor \dfrac{m-n}{d1} \right\rfloor, m n(d2) \end{cases}A⎩⎨⎧−1,m−n(d1),⌊d1m−n⌋,mn(d1)n(d1)≤m≤n(d2)mn(d2)时间复杂度和空间复杂度皆为O ( 1 ) O(1)O(1)。3. 代码usingSystem;classT663578{longn,m,d;publicstaticvoidMain(){varinputConsole.ReadLine().Split();nConvert.ToInt64(input[0]);mConvert.ToInt64(input[1]);dConvert.ToInt64(input[2]);longmin_costn*(d1);if(mmin_cost){Console.Write(-1);}elseif(mn*(d2)){Console.Write(m-min_cost);}else{Console.Write((m-n)/(d1));}}}
