本帖最后由 zhangjinxuan 于 2022-9-15 19:02 编辑
破案了!
对于2题:
测试程序:#include <bits/stdc++.h>
using namespace std;
struct Person {
int num, next;
}p[100001];
int main() {
int m, n, count = 0;
scanf("%d%d", &m, &n);
for (int i = 1; i < m; ++i) {
p[i].num = i;
p[i].next = i + 1;
}
p[m].num = m;
p[m].next = 1;
int cur = 1;
int pre = m;
while (p[cur].next != cur) {
++count;
if (count == n) {
p[pre].next = p[p[pre].next].next;
count = 0;
} else
pre = cur;
cur = p[cur].next;
}
printf("%d\n", p[cur].num);
}
输入&输出:
的确是第4个人最后出列!
对于3题:
的确不严谨,在m >= 1的情况下,确实会被重置m - 1次,但像你说的m == 0那就不一样了
对于4题:
如果,他真的是O(n log n),执行100000的数据大小肯定没有问题
但是,我们来测试一下(别忘了,是报到n出列,不是有n个人)
输入&输出:自己试试,一定超时,因为 O(n log n) 的算法极大概率有二分
你在代码里看见二分的影子了吗?
你可能会说:巧合,时间复杂度是估出来的
错!
不行你试试m = 50000,n = 10000,都超时!
所以这道选择题,是书错![不是书错,就是我错...]
结论:2题是对的,3题不严谨,4题不是书错就是我错
[对了,这是第几页,我也看看] |