运送物资
时间限制：1.0 s
内存限制：512.0 MB
题面描述
小杨管理着 m 辆货车，每辆货车每天需要向 A 市和 B 市运送若干次物资。小杨同时拥有 n 个运输站点，这些站点位于 A 市和 B 市之间。
每次运送物资时，货车从初始运输站点出发，前往 A 市或 B 市，之后返回初始运输站点。A 市、B 市和运输站点的位置可以视作数轴上的三个点，其中 A 市的坐标为 0，B 市的坐标为 x ，运输站点的坐标为 p 且有 0<p<x，货车每次去 A 市运送物资的总行驶路程为 2p，去 B 市运送物资的总行驶路程为 2(x−p)。
对于第 i 个运输站点，其位置为 pi且至多作为 ci辆车的初始运输站点。小杨想知道，在最优分配每辆货车的初始运输站点的情况下，所有货车每天的最短总行驶路程是多少。
输入格式
第一行包含三个正整数 n,m,x，代表运输站点数量，货车数量和两市距离。
之后 n 行，每行包含两个正整数 pi,ci，代表第 i 个运输站点的位置和最多容纳车辆数。
之后 m 行，每行包含两个正整数 ai,bi，代表第 i 辆货车每天需要向 A 市运送 ai次物资，向 B 市运送 bi次物资。
输出格式
输出一个正整数，代表所有货车每天的最短总行驶路程。
输入样例
3 4 10 1 1 2 1 8 3 5 3 7 2 9 0 1 10000
输出样例
40186
样例解释
第 1 辆车的初始运输站点为站点 3，第 2 辆车的初始运输站点为站点 2。第 3 辆车的初始运输站点为站点 1，第 4 辆车的初始运输站点为站点 3。此时总行驶路程最短，为 40186。
对于全部数据，保证有 1≤n,m≤105,2≤x≤108,0<pi<x,1≤ci≤105,0≤ai,bi≤105。数据保证∑ci≥m。
相似题推荐
执行如下代码，会输出 钢琴：叮咚叮咚 和 吉他：咚咚当当 。这体现了面向对象编程的（ ）特性。
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． 代码运行出现错误 |
