题目
小F是A市的市长，正在计划在A市新建一个火车站以方便市民的日常出行。市区内的街道布局十分规整，形成网格状。从一个位置[x1, y1]到另一个位置[x2, y2]的距离计算方法为 |x1 - x2| + |y1 - y2|，即曼哈顿距离。
在初步考察后，市政府列出了M个可能的火车站建设点。为了使得市民到火车站的总旅行时间最短，小F希望选出一个最优位置作为火车站的地址。
请你帮助小F计算出哪一个位置最适合建设新火车站。
N: 市民的总人数。M: 可建设火车站的备选位置数。citizens: 一个列表，每个元素是一个元组[x_i, y_i]，表示第i位市民的居住位置。locations: 一个列表，每个元素是一个元组[p_i, q_i]，表示第i个备选的火车站位置。
如果有多个火车站最优，那么选择第一次出现的那个。
demo
def solution(n, m, citizens, locations):
min_total_time = float('inf')
optimal_location = None
for location in locations:
total_time = 0
for citizen in citizens:
distance = abs(citizen[0] - location[0]) + abs(citizen[1] - location[1])
total_time += distance
if total_time < min_total_time:
min_total_time = total_time
optimal_location = location
return optimal_location
if __name__ == "__main__":
# You can add more test cases here
citizens1 = [[-1, -1], [-1, 1], [1, -1], [1, 1]]
locations1 = [[3, 2], [1, 0], [0, 0]]
print(solution(4, 3, citizens1, locations1) == [1, 0])题目
demo
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int solution(int n) {
int count = 0;
while (n > 1) {
if (n % 2 == 0) {
count += n / 2;
n /= 2;
} else {
count += (n - 1) / 2;
n = (n - 1) / 2 + 1;
}
}
return count;
}
int main() {
cout << (solution(7) == 6) << endl;
cout << (solution(14) == 13) << endl;
cout << (solution(1) == 0) << endl;
return 0;
}后记
做题做少了🤮 注意题目里面“当前队列” ，下面是AI给的建议
代码分析
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int solution(int n) {
int count = 0;
if (n % 2 != 0) {
count += ((n - 1) / 2);
for (int i = n; i >= 1;) {
count += ((n - 1) / 2 + 1) / 2;
i = (i - 1) / 2 + 1;
}
} else {
count += (n / 2);
for (; n >= 1;) {
count += (n / 2) / 2;
n = (n - 1) / 2 + 1;
}
}
return count;
}
int main() {
cout << (solution(7) == 6) << endl;
cout << (solution(14) == 13) << endl;
cout << (solution(1) == 0) << endl;
return 0;
}
问题点
- 循环条件错误：在
for循环中，i应该递减而不是递增。- 循环条件错误：
for循环的条件应该是i > 1而不是i <= 1。- 计数逻辑错误：在每次循环中，你应该累加当前轮的比赛次数，而不是累加下一轮的比赛次数。
- 初始条件错误：在奇数情况下，初始的
count计算是正确的，但后续的累加逻辑有误。修改建议
- 修正循环条件：确保循环条件正确。
- 修正计数逻辑：每次循环中累加当前轮的比赛次数。
- 简化逻辑：可以使用一个简单的循环来处理，而不是嵌套的
for循环。修改后的代码
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int solution(int n) {
int count = 0;
while (n > 1) {
if (n % 2 == 0) {
count += n / 2;
n /= 2;
} else {
count += (n - 1) / 2;
n = (n - 1) / 2 + 1;
}
}
return count;
}
int main() {
cout << (solution(7) == 6) << endl;
cout << (solution(14) == 13) << endl;
cout << (solution(1) == 0) << endl;
return 0;
}
解释
- 循环条件：
while (n > 1)确保当n大于 1 时继续循环。- 偶数情况：如果
n是偶数，累加n / 2场比赛，并将n减半。- 奇数情况：如果
n是奇数，累加(n - 1) / 2场比赛，并将n更新为(n - 1) / 2 + 1。这样修改后，代码应该能够正确计算出比赛的总配对次数。
