先尽量买完整套餐，再在很小的剩余金额里枚举额外物品数。
OJ: luogu
题目 ID: P6188
难度:普及/提高-
标签:数学枚举
日期: 2026-06-18 21:30
题意
用 n 元班费购买圆规、笔和笔记本，价格分别是 7,4,3 元。
要求正好花完钱，并且按优先级依次最大化：
min(a,b,c)a+b+c
输出最优方案；若无解输出 -1。
思路
先看一个可以直接验证想法的朴素解：
直接枚举所有满足 7a+4b+3c=n 的三元组，再按题目优先级更新答案。
cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
int best_min = -1;
int best_cnt = -1;
int ans_a = -1, ans_b = -1, ans_c = -1;
for (int a = 0; 7 * a <= n; a++) {
for (int b = 0; 7 * a + 4 * b <= n; b++) {
int left = n - 7 * a - 4 * b;
if (left % 3) continue;
int c = left / 3;
int mn = min(a, min(b, c));
int cnt = a + b + c;
if (mn > best_min || (mn == best_min && cnt > best_cnt)) {
best_min = mn;
best_cnt = cnt;
ans_a = a;
ans_b = b;
ans_c = c;
}
}
}
if (best_min == -1) {
cout << -1 << '\n';
} else {
cout << ans_a << ' ' << ans_b << ' ' << ans_c << '\n';
}
return 0;
}关键在于把答案拆成“完整套餐 + 额外购买”。
如果先买 t 套 (1,1,1)，就会花掉 14t 元。
而题目第 2 条本质上就是要求这个 t 尽量大。
于是只要先取最大的可行 t，再在剩余金额里让额外件数尽量多即可。
这时剩余金额的范围很小，直接枚举补充方案就够了。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
int t = n / 14;
int rem = n % 14;
if (rem == 1 || rem == 2 || rem == 5) {
t--;
rem += 14;
}
if (t < 0) {
cout << -1 << '\n';
return 0;
}
int best_a = -1, best_b = -1, best_c = -1;
int best_cnt = -1;
for (int a = 0; 7 * a <= rem; a++) {
for (int b = 0; 7 * a + 4 * b <= rem; b++) {
int left = rem - 7 * a - 4 * b;
if (left % 3) continue;
int c = left / 3;
int cnt = a + b + c;
if (cnt > best_cnt) {
best_cnt = cnt;
best_a = a;
best_b = b;
best_c = c;
}
}
}
if (best_cnt == -1) {
cout << -1 << '\n';
return 0;
}
cout << t + best_a << ' ' << t + best_b << ' ' << t + best_c << '\n';
return 0;
}复杂度
主解只在常数范围内枚举，时间复杂度
总结
这题的核心是先按“成套数”拆分，再在小剩余里补最优方案。