sakura 技术分享 2022-06-14

贪心：最长独立生活天数

最长独立生活天数

小易为了向他的父母表现他已经长大独立了,他决定搬出去自己居住一段时间。一个人生活增加了许多花费: 小易每天必须吃一个水果并且需要每天支付x元的房屋租金。当前小易手中已经有f个水果和d元钱,小易也能去商店购买一些水果,商店每个水果售卖p元。小易为了表现他独立生活的能力,希望能独立生活的时间越长越好,小易希望你来帮他计算一下他最多能独立生活多少天。
输入描述:

输入包括一行,四个整数x, f, d, p(1 ≤ x,f,d,p ≤ 2 * 10^9),以空格分割

输出描述:

输出一个整数, 表示小易最多能独立生活多少天。

思路：这个题可以转换为纯数学函数，假设最多能存活 N 天，则：

$n * x + (n - f) * p \leq d$

得出：

$n \leq (d + f p) / (x + p)$

直接将此算数运算纳入方法中，向下取整即可。

注意：根据方程会发现，有 n > (d/x) 的情况，而（d/x）是不吃水果的租房最大天数，不能超过这个数。方程结果中会出现的原因是 f 的值“匀”给了 d 。而实际上已经拥有的水果是无法换成现金来抵消房租的。

所以代码已经呼之欲出了：

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});
function solution(x, f, d, p) {
    // 当数据值过大，会溢出
    // 例如：1 1000000000 2000000000 1000000000，
    // 实际应该是输出 1000000000, javascript计算结果为 1000000001。
    let res = Math.floor((d+f*p)/(x+p))  // 贪心结果
    let pay = Math.floor(d/x)  // 租房最大天数
    return res < f ? pay : res
}

rl.on('line', function(line) { 
    let datas = line.trim().split(' ').map(item => parseInt(item))
     //编码
    if (datas.length < 4)  return null;
    let result = solution(datas[0], datas[1],datas[2], datas[3])
    console.log(result); //输出结果 
    process.exit(0);  
});
// 2 17 20 1
// 10