跳转至

2303. 计算应缴税款总额

题目描述

给你一个下标从 0 开始的二维整数数组 brackets ，其中 brackets[i] = [upperi, percenti] ，表示第 i 个税级的上限是 upperi ，征收的税率为 percenti 。税级按上限 从低到高排序（在满足 0 < i < brackets.length 的前提下，upperi-1 < upperi）。

税款计算方式如下：

  • 不超过 upper0 的收入按税率 percent0 缴纳
  • 接着 upper1 - upper0 的部分按税率 percent1 缴纳
  • 然后 upper2 - upper1 的部分按税率 percent2 缴纳
  • 以此类推

给你一个整数 income 表示你的总收入。返回你需要缴纳的税款总额。与标准答案误差不超 10-5 的结果将被视作正确答案。

 

示例 1：

输入：brackets = [[3,50],[7,10],[12,25]], income = 10
输出：2.65000
解释：
前 $3 的税率为 50% 。需要支付税款 $3 * 50% = $1.50 。
接下来 $7 - $3 = $4 的税率为 10% 。需要支付税款 $4 * 10% = $0.40 。
最后 $10 - $7 = $3 的税率为 25% 。需要支付税款 $3 * 25% = $0.75 。
需要支付的税款总计 $1.50 + $0.40 + $0.75 = $2.65 。

示例 2：

输入：brackets = [[1,0],[4,25],[5,50]], income = 2
输出：0.25000
解释：
前 $1 的税率为 0% 。需要支付税款 $1 * 0% = $0 。
剩下 $1 的税率为 25% 。需要支付税款 $1 * 25% = $0.25 。
需要支付的税款总计 $0 + $0.25 = $0.25 。

示例 3：

输入：brackets = [[2,50]], income = 0
输出：0.00000
解释：
没有收入，无需纳税，需要支付的税款总计 $0 。

 

提示：

  • 1 <= brackets.length <= 100
  • 1 <= upperi <= 1000
  • 0 <= percenti <= 100
  • 0 <= income <= 1000
  • upperi 按递增顺序排列
  • upperi 中的所有值 互不相同
  • 最后一个税级的上限大于等于 income

解法

方法一：模拟

思考

税级按上限递增且最后一级覆盖全部收入，因此税额由各档实际落入的金额唯一确定。\(brackets\) 至多 \(100\) 档，按序扫描即可。

第 \(i\) 档的应纳税基数是 \(\min(income, upper_i)\) 与上一档上限之差（若为负则该档未触及）。乘以税率并累加，最后除以 \(100\) 得到实缴税款。无需回溯或预计算。

我们遍历 brackets，对于每个税级，计算该税级的税额，然后累加即可。

时间复杂度 \(O(n)\)，其中 \(n\) 为 brackets 的长度。空间复杂度 \(O(1)\)。

1
2
3
4
5
6
7
class Solution:
    def calculateTax(self, brackets: List[List[int]], income: int) -> float:
        ans = prev = 0
        for upper, percent in brackets:
            ans += max(0, min(income, upper) - prev) * percent
            prev = upper
        return ans / 100

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    public double calculateTax(int[][] brackets, int income) {
        int ans = 0, prev = 0;
        for (var e : brackets) {
            int upper = e[0], percent = e[1];
            ans += Math.max(0, Math.min(income, upper) - prev) * percent;
            prev = upper;
        }
        return ans / 100.0;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    double calculateTax(vector<vector<int>>& brackets, int income) {
        int ans = 0, prev = 0;
        for (auto& e : brackets) {
            int upper = e[0], percent = e[1];
            ans += max(0, min(income, upper) - prev) * percent;
            prev = upper;
        }
        return ans / 100.0;
    }
};

1
2
3
4
5
6
7
8
9
func calculateTax(brackets [][]int, income int) float64 {
    var ans, prev int
    for _, e := range brackets {
        upper, percent := e[0], e[1]
        ans += max(0, min(income, upper)-prev) * percent
        prev = upper
    }
    return float64(ans) / 100.0
}

1
2
3
4
5
6
7
8
9
function calculateTax(brackets: number[][], income: number): number {
    let ans = 0;
    let prev = 0;
    for (const [upper, percent] of brackets) {
        ans += Math.max(0, Math.min(income, upper) - prev) * percent;
        prev = upper;
    }
    return ans / 100;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
impl Solution {
    pub fn calculate_tax(brackets: Vec<Vec<i32>>, income: i32) -> f64 {
        let mut res = 0f64;
        let mut pre = 0i32;
        for bracket in brackets.iter() {
            res += f64::from(income.min(bracket[0]) - pre) * f64::from(bracket[1]) * 0.01;
            if income <= bracket[0] {
                break;
            }
            pre = bracket[0];
        }
        res
    }
}

评论