小 A 要买 n个商品，每个商品价值为ai小 A 从抽奖得到了m张优惠券，其中第i张优惠券可以将商品价格降低到之前的bi/100倍（优惠券可叠加使用）。但商家肯定不会让小 A 花费太少的钱——那样就亏本了，所以给定一个整数k表示一个商品最多可以使用的优惠券张数。请输出最小的花费的钱数保留一位小数。c++代码

以下是C++代码实现：

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 1e6 + 5;
int n, m, k;
double a[MAXN], b[MAXN], c[MAXN], d[MAXN];
double f[MAXN];
int q[MAXN];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    cin >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> b[i] >> c[i];
        d[i] = 1.0 * b[i] / c[i];
    }
    cin >> k;

    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i++)
    {
        while (hh <= tt && i - q[hh] > k) hh++;
        while (hh <= tt && d[i] < d[q[tt]]) tt--;
        q[++tt] = i;
        if (i >= k + 1)
            f[i] = f[q[hh]] + a[i] * d[q[hh]];
    }

    printf("%.1lf", f[n]);
    return 0;
}

其中，$a_i$ 表示第 $i$ 个商品的原价，$b_i$ 表示第 $i$ 张优惠券可以减免的金额，$c_i$ 表示第 $i$ 张优惠券的面额，即减免后的金额为 $b_i/c_i$，$k$ 表示一个商品最多可以使用的优惠券张数。

首先，我们将面额和折扣率的比值计算出来，用数组 $d$ 存储。然后采用单调队列的方式进行动态规划。

定义 $f_i$ 表示前 $i$ 个商品使用优惠券后的最小花费。单调队列中存储的是前 $i$ 个商品中，最小的 $f_j+d_j \times a_i$，其中 $j=i-k, i-k+1, \cdots, i-1$。

对于每个 $i$，我们需要判断队首元素是否在 $i-k, i-k+1, \cdots, i-1$ 中，如果不在则需要出队。然后再将当前元素插入队尾，但要保证队列中的元素按照 $d_j$ 的大小单调不降。队首元素就是最小的 $f_j+d_j \times a_i$，最后的答案就是 $f_n$。