跳到主要内容

抵押契约

题目描述​

有一张购物清单，用一个数组 nums 表示，其中 nums[i] 表示第 i 件物品的原价。你按顺序依次买下这些物品。

公司提供一种"抵押契约"机制，并给出两个参数：

  • K：每当原价累计金额每满 K，即可获得 1 张抵押契约。
  • D：每张抵押契约在结算时可抵扣的金额。

抵押契约的使用规则如下：

  1. 发放规则：原价累计金额每满 K 获得 1 张契约。已经兑换过的累计金额不再重复计算。
  2. 时机限制：当天获得的契约从下一件物品开始才能使用，不能用于当前物品。
  3. 门槛限制：当前物品原价 price >= D 时，才可使用抵押契约。
  4. 抵扣规则：使用 1 张契约可抵扣 D，当前物品实际支付 price - D。
  5. 数量限制：每件物品最多使用 1 张契约。

请计算最终实际支付的总金额以及剩余的抵押契约数目。

输入描述​

第一行包含三个整数 K、D、m，分别表示发券阈值、单张抵扣金额、物品数量。

第二行包含 m 个整数，表示每件物品的原价 nums[i]。

  • 1 ≤ m ≤ 10^5
  • 1 ≤ K, D ≤ 10^9
  • 1 ≤ nums[i] ≤ 10^9

输出描述​

输出一行，包含两个整数，分别表示最终实际支付的总金额和剩余的抵押契约数目，整数之间用空格隔开。

示例​

输入：
10 3 3
6 8 4

输出：
15 0

解释:
- 第0件 price=6：无券，支付 6，累计原价 sum=6，未满 K，无新券。此时总支付 6，券 0。
- 第1件 price=8：无券，支付 8，累计原价 sum=14，满 10 获得 1 张券，sum 余 4。此时总支付 14，券 1。
- 第2件 price=4：有券且 4 ≥ 3，使用 1 张券，支付 4-3=1，券归 0。累计原价 sum=8，未满 K，无新券。
最终支付 6+8+1 = 15，剩余契约 0。

解题思路​

贪心 + 模拟

按照题意顺序遍历每件物品，维护三个变量：

  1. total：实际支付的总金额
  2. coupons：当前持有的抵押契约数
  3. sum：尚未兑换成契约的累计原价零头

对每件物品 price：

  1. 先尝试用旧券：若 coupons > 0 且 price >= D，则使用 1 张券，total += price - D，coupons--；否则 total += price。
  2. 再累计并发放新券：sum += price，本次获得 sum / K 张新券，coupons += sum / K，并令 sum %= K 保留尚未兑换的零头。

关键点：sum %= K 不可省略。若只写 coupons += sum / K 而不取模，已兑换过的累计金额会继续留在 sum 中，导致同一笔金额被重复兑换成多张契约（例如示例1中第3件会错误地再发一张券）。

时间复杂度: O(m) 空间复杂度: O(1)（若不存储 nums）

C++ 解法​

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    long long K, D;
    int m;
    cin >> K >> D >> m;

    // 读取每件物品的原价
    vector<long long> nums(m);
    for (int i = 0; i < m; i++) {
        cin >> nums[i];
    }

    long long total = 0;    // 实际支付总金额
    long long coupons = 0;  // 当前抵押契约数
    long long sum = 0;      // 尚未兑换的累计原价零头

    for (int i = 0; i < m; i++) {
        long long price = nums[i];

        // 1. 先尝试使用之前获得的抵押契约
        if (coupons > 0 && price >= D) {
            total += price - D;
            coupons--;
        } else {
            total += price;
        }

        // 2. 再累计原价，每满 K 获得一张新契约（新券下一件才能用）
        sum += price;
        coupons += sum / K;
        sum %= K;   // 关键：扣掉已兑换部分，防止重复发券
    }

    // 输出：实际支付金额 剩余契约数
    cout << total << " " << coupons << endl;

    return 0;
}