NOIP 提高组初赛 · NOIP 2018 提高组初赛试题 第 23 题

完善程序

一只小猪要买 $N$ 件物品（$N$ 不超过 $1000$）。

它要买的所有物品在两家商店里都有卖。第 $i$ 件物品在第一家商店的价格是 $a_i$ ，在第二家商店的价格是 $b_i$ ，两个价格都不小于 $0$ 且不超过 $10000$。如果在第一家商店买的物品的总额不少于 $50000$，那么在第一家店买的物品都可以打 $95$ 折（价格变为原来的 $0.95$ 倍）。

求小猪买齐所有物品所需最少的总额。

输入：第一行一个数 $N$。接下来 $N$ 行，每行两个数。第 $i$ 行的两个数分别代表 $a_i, b_i$。

输出：输出一行一个数，表示最少需要的总额，保留两位小数。

试补全程序。

#include <cstdio>
#include <cstdlib>
using namespace std;

const int Inf = 1000000000;
const int threshold = 50000;
const int maxn = 1000;

int n, a[maxn], b[maxn];
bool put_a[maxn];
int total_a, total_b;

double ans;
int f[threshold];

int main() {
    scanf("%d", &n);
    total_a = total_b = 0;
    for (int i = 0; i < n; ++i) {
        scanf("%d%d", a + i, b + i);
        if (a[i] <= b[i]) total_a += a[i];
        else total_b += b[i];
    }
    ans = total_a + total_b;
    total_a = total_b = 0;
    for (int i = 0; i < n; ++i) {
        if ( ① ) {
            put_a[

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题本质是贪心预处理加背包DP。先按单价把物品分好摊，算出商店A的总额；若总额不够50000，就考虑把原本在B买且B更便宜的那些物品‘切换’到A，用0-1背包求达到各额外消费额的最小代价，最后对比打折与不打折两种方案取最优。

最容易栽跟头的地方有三处：一是把折扣条件理解成‘只要有一件商品买了就打折’，其实必须商店A的总消费额≥50000才触发；二是切换时只盯着总价差，忽略了切换后商店A总额增加、商店B总额减少，导致额外成本算错；三是DP状态定义混淆，f[j]里的j代表的是‘额外在A消费的数量’，不是总消费，初始化时要把j<a[i]的位置设为INF，否则背包会越界或把不可能状态当成可行。

考点与命题视角

这道题考的是分支结构、循环结构以及简单动态规划（0-1背包）的综合运用。命题人喜欢在‘打折条件’上挖坑：很多人会以为只要总价超过某个数就能打折，或者误以为每件商品都能单独打折。实际上，只有当第一家商店的购买总额达到50000时，这家店的所有商品才能打95折。第二家商店无论多少都不打折。

核心思路：贪心 + 背包

1. 贪心预处理：每件物品先在两家店挑便宜的买。如果$a_i \le b_i$，默认在店1买；否则在店2买。此时算出店1的总额$total\_a$和店2的总额$total\_b$。 2. 判断折扣：如果$total\_a \ge 50000$，直接输出$0.95\times total\_a + total\_b$。 3. 考虑切换：如果$total\_a < 50000$，说明店1不够折扣线。这时只能把那些原本在店2买且店2更便宜的物品（即$a_i > b_i$）切换到店1。切换的代价是：店1增加$a_i$，店2减少$b_i$，额外成本为$a_i - b_i$（注意：切换后店1总额增加，可能触发折扣，但折扣是全局生效的，所以DP里我们只记录‘额外在店1消费’的最小成本，最后统一算打折效果）。 4. 背包DP：用$f[j]$表示额外在店1消费$j$元时的最小额外成本。$j$的范围是$0 \sim 49999$（因为超过50000的部分其实已经触发折扣，不需要再算额外成本，DP只负责把店1总额‘补’到50000所需的增量）。转移方程是经典的0-1背包： $$f[j] = \min(f[j], f[j-a_i] + a_i - b_i)$$ 注意循环要从大到小，保证每个物品只选一次。 5. 最终答案：遍历所有可能的额外消费$j$，计算$0.95\times(total\_a + j) + (total\_b - \text{已切换的B总额}) + f[j]$，取最小值。如果什么都不切换，就是原方案。