【编程题1】此题是一道关于二维平面上找“最大”点的问题。给定一组不重复的点，我们需要找出所有“最大”的点，即不存在任何点位于当前点的右上方。解决这个问题的关键在于理解题意，并能有效地进行排序和比较。
我们可以将所有点按x坐标排序。然后，对于每一个点，我们检查其右上方是否存在其他点。这可以通过在遍历过程中维护当前最大y坐标来实现。当遇到一个点的y坐标大于或等于当前最大y坐标时，这个点就是“最大”的。因此，我们需要编写一个算法，它能够对点进行排序，并进行遍历以找出所有满足条件的点。
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
struct Point {
int x, y;
};
bool compareX(const Point &a, const Point &b) {
return a.x < b.x;
}
bool isMax(const Point &p, const std::vector<Point> &points) {
for (const Point &q : points) {
if (q.x > p.x || (q.x == p.x && q.y >= p.y)) {
return false;
}
}
return true;
}
std::vector<Point> findMaxPoints(std::vector<Point> points) {
std::sort(points.begin(), points.end(), compareX);
std::vector<Point> maxPoints;
int maxY = -1;
for (const Point &p : points) {
if (p.y > maxY || (p.y == maxY && p.x > maxYX)) {
maxPoints.push_back(p);
maxY = p.y;
}
}
return maxPoints;
}
int main() {
int N;
std::cin >> N;
std::vector<Point> points(N);
for (int i = 0; i < N; ++i) {
std::cin >> points[i].x >> points[i].y;
}
std::vector<Point> maxPoints = findMaxPoints(points);
for (const Point &p : maxPoints) {
std::cout << p.x << " " << p.y << std::endl;
}
return 0;
}
```
【编程题2】这道题要求找到一个数组区间，使得区间内最小值乘以区间内所有数的和最大。这是一个经典的动态规划问题，可以通过动态规划数组dp[i]表示以第i个元素结尾的子数组的最大乘积来解决。对于每个元素，我们需要计算两种情况：包含当前元素和不包含当前元素的子数组的最大乘积。
```cpp
#include <iostream>
#include <vector>
using namespace std;
int maxProduct(vector<int>& nums) {
int n = nums.size();
vector<int> dp1(n), dp2(n);
dp1[0] = dp2[0] = nums[0];
for (int i = 1; i < n; ++i) {
dp1[i] = max(nums[i] * dp1[i - 1], nums[i] * dp2[i - 1]);
dp2[i] = min(nums[i] * dp1[i - 1], nums[i] * dp2[i - 1]);
}
int ans = dp1[n - 1];
for (int i = 1; i < n; ++i) {
ans = max(ans, dp1[i] / nums[i]);
}
return ans;
}
int main() {
int n;
cin >> n;
vector<int> nums(n);
for (int& num : nums) {
cin >> num;
}
cout << maxProduct(nums) << endl;
return 0;
}
```
【编程题3】此题涉及到多任务调度问题，需要模拟PM和程序员的行为。我们可以使用优先队列来解决这个问题，优先级最高的任务会被优先处理。对于每个PM，记录他们的想法和优先级，然后按照优先级和时间进行排序。程序员会按顺序处理这些任务。
```cpp
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct Idea {
int pmId, time, priority, reqTime;
};
bool compareIdea(const Idea &a, const Idea &b) {
if (a.priority != b.priority) {
return a.priority > b.priority;
} else if (a.time != b.time) {
return a.time < b.time;
} else {
return a.pmId < b.pmId;
}
}
int solve(vector<Idea> &ideas, int m) {
priority_queue<Idea, vector<Idea>, decltype(compareIdea)*> pq(compareIdea);
for (Idea &idea : ideas) {
pq.push(idea);
}
int currentTime = 0, result[ideas.size()];
while (!pq.empty()) {
Idea topIdea = pq.top();
pq.pop();
if (currentTime >= topIdea.time) {
result[topIdea.pmId] = currentTime + topIdea.reqTime;
currentTime = result[topIdea.pmId];
} else {
currentTime = topIdea.time;
result[topIdea.pmId] = currentTime + topIdea.reqTime;
}
}
return result;
}
int main() {
int n, m, p;
cin >> n >> m >> p;
vector<Idea> ideas(p);
for (Idea &idea : ideas) {
cin >> idea.pmId >> idea.time >> idea.priority >> idea.reqTime;
}
for (int i = 0; i < p; ++i) {
cout << solve(ideas, m)[i] << endl;
}
return 0;
}
```
【问答题】这道题目要求找到一棵树中节点数最多的层，并返回该层的深度。给定的代码存在错误，例如变量名未正确初始化。下面是修复后的代码：
```cpp
#include <iostream>
#include <vector>
using namespace std;
struct Node {
vector<Node*> sons;
};
void dfsFind(Node* node, int depth, int counter[], int maxDepth) {
counter[depth]++;
for (Node* child : node->sons) {
dfsFind(child, depth + 1, counter, maxDepth);
}
}
int findMaxNodesLayer(Node* root, int maxDepth) {
int depCounter[maxDepth + 1] = {0};
dfsFind(root, 0, depCounter, maxDepth);
int maxNodes = 0, maxDepthIndex = 0;
for (int i = 1; i <= maxDepth; i++) {
if (depCounter[i] > maxNodes) {
maxNodes = depCounter[i];
maxDepthIndex = i;
}
}
return maxDepthIndex;
}
int main() {
// 读取树结构和最大深度的代码
// ...
int maxDepthIndex = findMaxNodesLayer(root, 100000);
cout << "The layer with the most nodes is at depth: " << maxDepthIndex << endl;
return 0;
}
```
以上代码修复了原始代码中的错误，并提供了正确的实现。`dfsFind`函数现在接受最大深度作为参数，`findMaxNodesLayer`函数正确地初始化了`depCounter`数组，并找到了节点数最多的层的深度。
