提高】推销员 显示标签 时间限制：C/C++ 1000MS，其他语言 2000MS 内存限制：C/C++ 128MB，其他语言 256MB 难度：提高 分数：100 OI排行榜得分：18(0.1*分数+2*难度) 出题人： 描述 阿明是一名推销员，他奉命到螺丝街推销他们公司的产品。螺丝街是一条死胡同，出口与入口是同一个，街道的一侧是围墙，另一侧是住户。螺丝街一共有N家住户，第i家住户到入口的距离为Si米。由于同一栋房子里可以有多家住户，所以可能有多家住户与入口的距离相等。阿明会从入口进入，依次向螺丝街的X家住户推销产品，然后再原路走出去。阿明每走1米就会积累1点疲劳值，向第i家住户推销产品会积累Ai点疲劳值。阿明是工作狂，他想知道，对于不同的X，在不走多余的路的前提下，他最多可以积累多少点疲劳值。 输入描述 第一行有一个正整数N，表示螺丝街住户的数量。 接下来的一行有N个正整数，其中第i个整数Si表示第i家住户到入口的距离。数据保证S1≤S2≤…≤Sn<108。 接下来的一行有N个正整数，其中第i个整数Ai表示向第i户住户推销产品会积累的疲劳值。数据保证Ai<103。 输出

```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; // 定义住户结构体，包含距离和疲劳值 struct House { int distance; int fatigue; }; // 比较函数，按疲劳值从大到小排序 bool compare(const House& a, const House& b) { return a.fatigue > b.fatigue; } int main() { int N; cin >> N; vector<House> houses(N); // 读取每家住户到入口的距离 for (int i = 0; i < N; ++i) { cin >> houses[i].distance; } // 读取向每家住户推销产品的疲劳值 for (int i = 0; i < N; ++i) { cin >> houses[i].fatigue; } // 对于不同的X值进行计算 for (int X = 1; X <= N; ++X) { vector<House> selected = houses; // 按疲劳值从大到小排序 sort(selected.begin(), selected.end(), compare); int maxDistance = 0; int totalSalesFatigue = 0; // 选择前X个疲劳值最大的住户 for (int i = 0; i < X; ++i) { totalSalesFatigue += selected[i].fatigue; maxDistance = max(maxDistance, selected[i].distance); } // 计算总疲劳值，走路疲劳值为往返 int totalFatigue = 2 * maxDistance + totalSalesFatigue; cout << totalFatigue << endl; } return 0; } ``` 代码解释： 1. 结构体 `House`：定义了一个 `House` 结构体来存储每家住户的距离和疲劳值。 2. 比较函数 `compare`：用于对住户按疲劳值从大到小排序。 3. 数据读取：先读取住户数量 `N`，接着读取每家住户到入口的距离，再读取向每家住户推销产品的疲劳值。 4. 主循环：对于不同的 `X` 值（从 1 到 `N`）进行计算： - 创建一个 `selected` 向量，将所有住户复制到其中。 - 对 `selected` 向量按疲劳值从大到小排序。 - 选择前 `X` 个疲劳值最大的住户，计算推销的总疲劳值和最大距离。 - 计算总疲劳值，包括往返走路的疲劳值和推销的疲劳值。 5. 输出结果：输出每个 `X` 值对应的最大疲劳值。 [2026-02-04 21:39:36 | AI问答 | 627点数解答]