Awa玩游戏

第一行一个正整数 $T$ ，表示游戏进行了 $T$ 次

对于每次游戏，第一行输入两个正整数 $N,M$ ，表示该局中参与游戏的人数，以及牌的总数，第二行输入 $N$ 个数，其中第一个数为Awa的手牌编号，之后为其他人的手牌编号。

C++(g++ 7.5.0) 解法, 执行用时: 721ms, 内存消耗: 784K, 提交时间: 2023-01-05 19:17:08

#include<iostream>
#include<algorithm>
using namespace std;
int a[100010];
int main()
{
	int T;
	scanf("%d",&T);
	int N, M, awanum;
	while (T--) {
		scanf("%d %d",&N,&M);
		for (int i = 1; i <= N; i++) 
			scanf("%d",&a[i]);
		//awa手牌号码
		awanum = a[1];
		sort(a + 1, a + 1 + N);
		//回合数
		int round = 1;
		int min = 1, max = M;
		int left = 1, right = N;
		while (left < right) {
			if (max - min == right - left)
				break;
			if (a[left] == min) {
				if (awanum == a[left]) break;
				left++;
			}
			if (a[right] == max)
			{
				if (awanum == a[right]) break;
				right--;
			}
			round++;
			min++;
			max--;
		}
		cout << round << endl;
	}
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 615ms, 内存消耗: 752K, 提交时间: 2022-12-30 17:06:52

#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
	int t, m , n,p[100010];
	cin >> t;
	while(t--)
	{
		cin >> n >> m;
		for(int i = 1; i <= n; i++) scanf("%d",&p[i]);
		int l = 1, r = m, ans = 1, x = 1, y = n, z = p[1];
		sort(p + 1, p + n + 1);
		while(x < y)
		{
			if(y - x == r - l) break;
			if(p[x] == l)
			{
				if(l == z) break;
				x++;
			}
			if(p[y] == r)
			{
				if(r == z) break;
				y--;
			}
			l ++, r--;
			ans++;
		}
		cout << ans << endl;
	}
	return 0;
}

详情