题目描述
A new game is coming for Alice and Bob! This time they're addicted to the game named Hearthstone-BETA, which is based on a sequence of numbers. In each move, Alice/Bob is only allowed to exchange the positions of ANY two numbers in the sequence. The two players operates alternately, and the one wins when he/she makes the sequence monotonic (non-strict increasing or decreasing).
Out of the principle of "lady first", Alice always moves first. As the best players ever, they two will obviously take the best strategy in the game. Would you tell us the results of the game under various initial states? Note that if the initial sequence is monotonic, then Alice will win.
输入格式
The input consists of multiple test data.
The first line of input contains an integer T(T≤50) , indicating the number of test cases.
Each test case starts with the length of the sequence N(N≤103) .
The following line consists of N integers (not exceed 105 ), which denotes the initial sequence of the game.
输出格式
Output one line for each test case, which is either `Alice Wins`, `Bob Wins`, or `Tie`.
输入样例
2
4
1 3 2 4
4
1 2 3 4输出样例
Alice Wins
Alice Wins博弈论, 由于可以随意改变两数位置, 所以Alice不能一步以内胜利即为平局, Bob则不可能胜利.
所以从两个方向各扫一遍整个序列, 寻找目标数列和胜利条件数列相差的个数即可.
#include <stdio.h>
#include <stdlib.h>
#define For(i,m,n) for(i=(m);i<(n);i++)
#define MIN(x,y) (x)<(y)?(x):(y)
#define MAXN 100005int a[MAXN], b[MAXN], c[MAXN];int cmp(const void* a, const void* b)
{return *(int *)a-*(int *)b;
}int cmp2(const void* a, const void* b)
{return *(int *)b-*(int *)a;
}main()
{int i, j, n, t, cnt, min;scanf("%d",&t);while(t--){cnt=0;scanf("%d",&n);For(i,0,n) scanf("%d",&a[i]), c[i]=b[i]=a[i];qsort(b,n,sizeof(int),cmp);qsort(c,n,sizeof(int),cmp2);For(i,0,n) if(a[i]!=b[i]) cnt++;min=cnt; cnt=0;For(i,0,n) if(a[i]!=c[i]) cnt++;min=MIN(min,cnt);if(min==0||min==2) puts("Alice Wins");else puts("Tie");}return 0;
}