小杨买饮料（2023.9C++六级）
时间限制：1.0 s
内存限制：128.0 MB
问题描述
小杨来到了一家商店，打算购买一些饮料。这家商店总共出售N种饮料，编号从0至N-1，其中编号为i的饮料售价ci元，容量li毫升。
小杨的需求有如下几点：
1. 小杨想要尽可能尝试不同种类的饮料，因此他希望每种饮料至多购买 1 瓶；
2. 小杨很渴，所以他想要购买总容量不低于L的饮料；
3. 小杨勤俭节约，所以在 1 和 2 的前提下，他希望使用尽可能少的费用。
方便起见，你只需要输出最少花费的费用即可。特别地，如果不能满足小杨的要求，则输出 no solution 。
输入描述
第一行两个整数N,L。
接下来N行，依次描述第i=0,1,...,N-1种饮料：每行两个整数ci,li。
输出描述
输出一行一个整数，表示最少需要花费多少钱，才能满足小杨的要求。特别地，如果不能满足要求，则输出 no
solution 。
特别提醒
在常规程序中，输入、输出时提供提示是好习惯。但在本场考试中，由于系统限定，请不要在输入、输出中附带任何提示信息。
样例输入 1
5 100
100 2000
2 50
4 40
5 30
3 20
样例输出 1
9
样例解释 1
小杨可以购买1,2,4号饮料，总计获得50+40+20=110毫升饮料，花费2+4+3=9元。
如果只考虑前两项需求，小杨也可以购买1,2,4号饮料，它们的容量总和为50+30+20=100毫升，恰好可以满足需求。但遗憾的是，这个方案需要花费2+5+3=10元。
样例输入 2
5 141
100 2000
2 50
4 40
5 30
3 20
样例输出 2
100
样例解释 2
1,2,3,4号饮料总计140毫升，如每种饮料至多购买 1 瓶，则恰好无法满足需求，因此只能花费100元购买0号饮料。
样例输入 3
4 141
2 50
4 40
5 30
3 20
样例输出 3
no solution
数据规模
对于40%的测试点，保证N≤20 ；1≤L≤100 ；li≤100。
对于70%的测试点，保证li≤100。
对于所有测试点，保证1≤N≤500 ；1≤L≤2000 ；1≤ci,li≤106。
相似题推荐
执行如下代码，会输出 钢琴：叮咚叮咚 和 吉他：咚咚当当 。这体现了面向对象编程的（ ）特性。
class Instrument {
public:
virtual void play() {
cout << "乐器在演奏声音" << endl;
}
virtual ~Instrument() {}
};
class Piano : public Instrument {
public:
void play() override {
cout << "钢琴：叮咚叮咚" << endl;
}
};
class Guitar : public Instrument {
public:
void play() override {
cout << "吉他：咚咚当当" << endl;
}
};
int main() {
Instrument* instruments[2];
instruments[0] = new Piano();
instruments[1] = new Guitar();
for (int i = 0; i < 2; ++i) {
instruments[i]->play();
}
for (int i = 0; i < 2; ++i) {
delete instruments[i];
}
return 0;
} | A． 继承 |
B． 封装 |
| C． 多态 |
D． 链接 |
在二叉排序树（Binary Search Tree, BST）中，假设节点值互不相同。给定如下搜索函数，以下说法一定正确的是（ ）。
bool find(Node* root, int x) {
while (root) {
if (root->val == x) return true;
root = (x < root->val) ? root->left : root->right;
}
return false;
} | A． 最坏情况下，访问结点数是O(logn) |
B． 最坏情况下，访问结点数是O(n) |
| C． 无论如何，访问结点数都不超过树高的一半 |
D． 一定比在普通二叉树中搜索快 |
0/1 背包（每件物品最多选一次）问题通常可用一维动态规划求解，核心代码如下。则下面说法正确的是（）。
for each item (w, v): for (int j = W; j >= w; --j) dp[j] = max(dp[j], dp[j-w] + v);
| A． 内层 j 必须从小到大，否则会漏解 |
B． 内层 j 必须从大到小，否则同一件物品会被用多次 |
| C． j 从大到小或从小到大都一样 |
D． 只要 dp 初始为 0 ，方向无所谓 |
下面代码实现了哈夫曼编码，则横线处应填写的代码是（ ）。
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
struct Symbol {
char ch; //字符
long long freq; //频率
string code; //哈夫曼编码
};
struct Node {
long long w; //权值
int l, r; //左右孩子（节点下标），-1 表示空
int sym; //叶子对应符号下标；内部节点为 -1
Node(long long _w = 0, int _l = -1, int _r = -1, int _sym = -1)
: w(_w), l(_l), r(_r), sym(_sym) {}
};
// 从 A(leafIdx) 和 B(internalIdx) 的队首取最小的一个节点下标
static int PopMinNode(const vector<Node>& nodes,
const vector<int>& leafIdx, int n, int& pA,
const vector<int>& internalIdx, int& pB)
{
if (pA < n && (pB >= (int)internalIdx.size() ||
nodes[leafIdx[pA]].w <= nodes[internalIdx[pB]].w))
{
return leafIdx[pA++];
}
else
{
return internalIdx[pB++];
}
}
// DFS 生成编码（左 0，右 1）
static void DFSBuildCodes(int u, const vector<Node>& nodes, Symbol sym[], string& path)
{
if (u == -1)
return;
if (nodes[u].sym != -1) // 叶子
{
sym[nodes[u].sym].code = path;
return;
}
path.push_back('0');
DFSBuildCodes(nodes[u].l, nodes, sym, path);
path.pop_back();
path.push_back('1');
DFSBuildCodes(nodes[u].r, nodes, sym, path);
path.pop_back();
}
int BuildHuffmanCodes(Symbol sym[], int n)
{
for (int i = 0; i < n; i++)
sym[i].code.clear();
if (n <= 0)
return -1;
// 只有一个字符：约定编码为 "0"
if (n == 1)
{
sym[0].code = "0";
return 0;
}
vector<Node> nodes;
nodes.reserve(2 * n);
// 1) 建立叶子节点
vector<int> leafIdx(n);
for (int i = 0; i < n; i++)
{
leafIdx[i] = (int)nodes.size();
nodes.push_back(Node(sym[i].freq, -1, -1, i));
}
// 2) 叶子按权值排序（A 队列）
sort(leafIdx.begin(), leafIdx.end(),
[&](int a, int b)
{
if (nodes[a].w != nodes[b].w)
return nodes[a].w < nodes[b].w;
return nodes[a].sym < nodes[b].sym; // 稳定一下
});
// B 队列（内部节点下标队列）
vector<int> internalIdx;
internalIdx.reserve(n);
int pA = 0, pB = 0;
// 3) 合并 n-1 次
for (int k = 1; k < n; k++)
{
int x = PopMinNode(nodes, leafIdx, n, pA, internalIdx, pB);
int y = PopMinNode(nodes, leafIdx, n, pA, internalIdx, pB);
int z = (int)nodes.size();
// =====================在此处填写代码=====================
}
int root = internalIdx.back();
// 4) DFS 生成编码
string path;
DFSBuildCodes(root, nodes, sym, path);
return root;
} A．nodes.push_back(Node(nodes[x].w + nodes[y].w, x, y, -1)); internalIdx.push_back(z); |
B．nodes.push_back(Node(nodes[x].w + nodes[y].w, x, y, -1)); leafIdx.push_back(z); |
C．internalIdx.push_back(z); nodes.push_back(Node(nodes[x].w + nodes[y].w, x, y, x+y)); |
D．nodes.push_back(Node(nodes[x].w + nodes[y].w, x, y, x+y)); leafIdx.push_back(z); |
关于以下代码，说法正确的是（ ）。
class Instrument {
public:
void play() {
cout << "乐器在演奏声音" << endl;
}
virtual ~Instrument() {}
};
class Piano : public Instrument {
public:
void play() override {
cout << "钢琴：叮咚叮咚" << endl;
}
};
class Guitar : public Instrument {
public:
void play() override {
cout << "吉他：咚咚当当" << endl;
}
};
int main() {
Instrument* instruments[2];
instruments[0] = new Piano();
instruments[1] = new Guitar();
for (int i = 0; i < 2; ++i) {
instruments[i]->play();
}
for (int i = 0; i < 2; ++i) {
delete instruments[i];
}
return 0;
} | A． 执行代码会输出两行，内容分别为： 钢琴：叮咚叮咚 和 吉他：咚咚当当 |
B． 执行代码会输出两行，内容分别为： 乐器在演奏声音 和 乐器在演奏声音 |
| C． 代码编译出现错误 |
D． 代码运行出现错误 |
