书店折扣问题

描述

这是Exercism中的题目。
书店对五本不同的书的售卖提供折扣：

每本书8美元
购买两本不同的书，得到5%的折扣
购买三本不同的书, 得到10%的折扣
购买四本不同的书, 得到20%的折扣
购买5本不同的书, 得到25%的折扣
根据用户购买的书，选择最优惠的折扣方案，并计算最终价格(美分)。
注意：一个5 + 3的方案的优惠折扣是35%，是不如4 + 4方案的40%折扣的

例如：
用户购买了8本书，其中2本第一种书，2本第二种书，2本第三种书，1本第四种书， 1本第五种书
折扣方案有两种：
第一种是5 + 3 的方案（一组以5本不同的书的折扣计算价格，一组以3本不同的书的折扣计算价格），优惠折扣是35%
第二种是4 + 4 的方案，优惠折扣是40%，
因第二种优惠力度较大，选择第二种方案, 计算最终价格: 4 * (100% - 20 %) * 800 * 2 = 5120

解题方案

总共有五种书，可以首先计算5种书中，用户每中购买了多少本
依次扣减最少本数种类的书，依次计算每种方案的数量
以上述示例为例：

每种书的数量从小到大排序：[1, 1, 2, 2, 2]
每本书扣减1: [0, 0, 1, 1, 1], 有一个5种不同书的方案
现在i最小的还是1，再次扣减1: [0, 0, 0, 0, 0], 有一个3种不同书的方案

如果存在5 + 3方案，则替代为4 + 4 方案
计算最终方案的价格

完整代码

pub fn lowest_price(books: &[u32]) -> u32 {
    // 存储每种书的数量
    let mut count = [0; 5];
    books.iter().for_each(|x| count[(x - 1) as usize] += 1);
    // 根据每种书的数量进行排序
    count.sort();

    // 获取购买方案, 
    // set[0]存储购买5本不同种类的书的方案数量，set[1]存储购买4本不同种类的书的方案数量...以此类推
    let mut sets = [0; 5];
    let mut cur = 0;
    for idx in 0..count.len() {
        sets[idx] = count[idx] - cur;
        cur += sets[idx];
    }

    // 计算4 + 4 方案代替 5 + 3方案的数量
    let numthreeinotfours = if sets[0] < sets[2] {
        sets[0]
    } else {
        sets[2]
    };

    // 计算i最终价格
    800 * sets[4] + 1520 * sets[3] + 2160 * (sets[2] - numthreeinotfours) + 2560 * (sets[1] + numthreeinotfours * 2) + 3000 * (sets[0] - numthreeinotfours)
}