小杨的握手问题（2023.9C++六级）
时间限制：1.0 s
内存限制：128.0 MB
问题描述
小杨的班级里共有N名同学，学号从0至N-1。
某节课上，老师安排全班同学进行一次握手游戏，具体规则如下：老师安排了一个顺序，让全班N名同学依次进入教室。每位同学进入教室时，需要和已经在教室内且学号小于自己的同学握手。
现在，小杨想知道，整个班级总共会进行多少次握手。
提示：可以考虑使用归并排序进行降序排序，并在此过程中求解。
输入描述
输入包含2行。第一行一个整数N，表示同学的个数；第二行N个用单个空格隔开的整数，依次描述同学们进入教室的顺序，每个整数在0~N-1之间，表示该同学的学号。
保证每位同学会且只会进入教室一次。
输出描述
输出一行一个整数，表示全班握手的总次数。
特别提醒
在常规程序中，输入、输出时提供提示是好习惯。但在本场考试中，由于系统限定，请不要在输入、输出中附带任何提示信息。
样例输入 1
4
2 1 3 0
样例输出 1
2
样例解释 1
2号同学进入教室，此时教室里没有其他同学。
1号同学进入教室，此时教室里有2号同学。1号同学的学号小于2号同学，因此他们之间不需要握手。
3号同学进入教室，此时教室里有1,2号同学。3号同学的学号比他们都大，因此3号同学需要分别和另外两位同学握手。
0号同学进入教室，此时教室里有1,2,3号同学。0号同学的学号比他们都小，因此0号同学不需要与其他同学握手。
综上所述全班一共握手0+0+2+0=2次。
样例输入 2
6
0 1 2 3 4 5
样例输出 2
15
样例解释 2
全班所有同学之间都会进行握手，因为每位同学来到教室时，都会发现他的学号是当前教室里最大的，所以他需要和教室里的每位其他同学进行握手。
数据规模
对于30%的测试点，保证N≤100。
对于所有测试点，保证2≤N≤3×105。
相似题推荐
执行如下代码，会输出 钢琴：叮咚叮咚 和 吉他：咚咚当当 。这体现了面向对象编程的（ ）特性。
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． 代码运行出现错误 |
