题目描述
blablabla
样例
#include<iostream>
#include<algorithm>
using namespace std;
/*
思考过程:
我简单地认为,是两个玩家交替地着拿石头,只需要看石头的堆数就可以了,
奇数就是Mike赢,偶数就是Joe赢。
这其中我默认,二者取石头的位子在下一次循环时,会重合,
即mike第一个拿,而在下一次面对第一堆石头时,是Joe拿,这是错误的。
且,我在思考中,我默认每个人拿的时候,都是把所有石头拿完。
下一次再到这个位置时,必定失败。
看他人思路后,
我发才察觉到,,奇数情况,我是正确的,但是偶数情况,我想得太简单了。
偶数情况,不存在我上面的那个下次循环会重合位置的情况,两个玩家取石头的位置都是固定的,即mike第一次在第一堆拿石头,下次循环到第一堆时,还是mike拿。
这样,我们就不能一次拿完了,否则mike必输。
因为,位置固定,所以我们在这个情况下比的是谁坚持得最久,最晚拿完石头。
也就是在原来的石堆中,最少石子的那一堆的位置下标,的奇偶性,决定了谁赢。
奇数,说明,mike最先拿完,Joe赢了,反之,Mike赢了。
这里我反糊涂了,以为谁先拿完,谁赢,困住了一会。
*/
int main() {
long long t, n,num,indx;
cin >> t;
while (t--) {
cin >> n;
long long min = 1e9 + 1;
for (int i = 1; i <= n; i++) {
scanf("%lld", &num);
if (num < min)min = num, indx = i;
}
if (n % 2 == 0) {
if (indx % 2 == 0)cout << "Mike" << endl;
else cout << "Joe" << endl;
}
else cout << "Mike" << endl;
}
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla