Battle Cows
题面翻译
题目描述
有 $ n $ 头奶牛参加编程比赛。奶牛 $ i $ 的 Cowdeforces 评级为 $ a_i $（奶牛们的评级全部不同）。它们最初处于 $ i $ 的位置。比赛由 $ n-1 $ 个比赛组成，规则如下所示：
- 第一场比赛是在位置 $ 1 $ 的奶牛和位置 $ 2 $ 的奶牛之间。
- 随后，每场比赛 $ i $ 在位置 $ i+1 $ 的奶牛和比赛 $ i-1 $ 的获胜者之间。
- 在每场比赛中，Cowdeforces 评级较高的奶牛获胜并进入下一场比赛。
你是奶牛 $ k $ 的主人。对你来说，赢得比赛并不重要。你希望你的奶牛在尽可能多的比赛中获胜。作为比赛组织者的熟人，你可以要求他们将你的奶牛与另一头奶牛交换一次位置，或者什么都不做。请问你的奶牛最多胜利几场？
输入格式
每个测试点都包含多组数据。第一行为数据组数 $ t $ （ $ 1 \le t \le 10^4 $ ）。
每组数据的第一行包含两个整数 $ n $ 和 $ k $ 表示奶牛的数量和你的奶牛的位置（ $ 2 \le n \le 10^5， 1 \le k \le n $ ）。
第二行包含 $ n $ 个整数 $ a_1，a_2，\ldots，a_n $ 表示奶牛的 Cowdeforces 评级（ $ 1 \le a_i \le 10^9 $ ）。保证 $ a_i $ 与 $ a_{i+1} $ 不同。
保证所有数据的 $ n $ 之和不超过 $ 10^5 $ 。
输出格式
对于每组数据，输出一个整数，表示奶牛 $ k $ 可以达到的最多胜利次数。
提示
在第一组数据中，应该什么都不做。设 $ a’ $ 是原始顺序中奶牛的 Cowdeforces 评级（你的奶牛评级会加粗）。
- 最初，$ a’ = [\mathbf{12}， 10， 14， 11， 8， 3] $ 。
- 你的奶牛与 Cowdeforces 评级为 $ 10 $ 的奶牛对战并获胜。现在 $ a’ = [\mathbf{12}， 14， 11， 8， 3] $ 。
- 你的奶牛与 Cowdeforces 评级为 $14$ 的奶牛对战，输掉了比赛。
你的奶牛赢得了 $ 1 $ 场比赛。在第二组数据中，应该将奶牛交换到位置 $ 3 $ 。然后，设 $ a’ $ 是交换后顺序中奶牛的 Cowdeforces 评级。
- 最初，$ a’ = [7， 2， \mathbf{12}， 10， 727， 13] $ .
- Cowdeforces 评级为 $ 7 $ 的奶牛与Cowdeforces评级为 $ 2 $ 的奶牛对战并获胜。现在 $ a’ = [7， \mathbf{12}， 10， 727， 13] $ .
- Cowdeforces 评级为 $ 7 $ 的奶牛与你的奶牛对战，你的奶牛获胜。$ a’ = [\mathbf{12}， 10， 727， 13] $ .
- 你的奶牛与 Cowdeforces 评级为 $ 10 $ 的奶牛对战并获胜。现在 $ a’ = [\mathbf{12}， 727， 13] $ .
- 你的奶牛与 Cowdeforces 评级为 $727$ 的奶牛对战，输掉了比赛。
你的奶牛赢得了 $ 2 $ 场比赛。
题目描述
ඞ
There are $ n $ cows participating in a coding tournament. Cow $ i $ has a Cowdeforces rating of $ a_i $ (all distinct), and is initially in position $ i $ . The tournament consists of $ n-1 $ matches as follows:
- The first match is between the cow in position $ 1 $ and the cow in position $ 2 $ .
- Subsequently, each match $ i $ is between the cow in position $ i+1 $ and the winner of match $ i-1 $ .
- In each match, the cow with the higher Cowdeforces rating wins and proceeds to the next match.
You are the owner of cow $ k $ . For you, winning the tournament is not important; rather, you want your cow to win in as many matches as possible. As an acquaintance of the tournament organizers, you can ask them to swap the position of your cow with another cow only once, or you can choose to do nothing.
Find the maximum number of wins your cow can achieve.
输入格式
Each test contains multiple test cases. The first line contains an integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The description of the test cases follows.
The first line of each test case contains two integers $ n $ and $ k $ ( $ 2 \le n \le 10^5, 1 \le k \le n $ ) — the number of cows and your cow’s index.
The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^9 $ ) — the Cowdeforces rating of the cows. It is guaranteed that $ a_i $ ‘s are pairwise different.
It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .
输出格式
For each test case, print one integer: the maximum number of wins cow $ k $ can achieve if you choose to swap (or do nothing) optimally.
样例 #1
样例输入 #1
3
6 1
12 10 14 11 8 3
6 5
7 2 727 10 12 13
2 2
1000000000 1
样例输出 #1
1
2
0
提示
In the first test case, it is optimal to do nothing. Let $ a’ $ be the Cowdeforces rating of the cows in the original order (with your cow’s rating bolded), then
- Initially, $ a’ = [\mathbf{12}, 10, 14, 11, 8, 3] $ .
- Your cow plays against the cow with Cowdeforces rating $ 10 $ and wins. $ a’ = [\mathbf{12}, 14, 11, 8, 3] $ .
- Your cow plays against the cow with Cowdeforces rating $ 14 $ and loses.
In total, your cow wins $ 1 $ match.In the second test case, it is optimal to swap your cow to position $ 3 $ . Then, let $ a’ $ be the Cowdeforces rating of the cows in the order after the swap.
- Initially, $ a’ = [7, 2, \mathbf{12}, 10, 727, 13] $ .
- The cow with Cowdeforces rating $ 7 $ plays against the cow with Cowdeforces rating $ 2 $ and wins. $ a’ = [7, \mathbf{12}, 10, 727, 13] $ .
- The cow with Cowdeforces rating $ 7 $ plays against your cow, and your cow wins. $ a’ = [\mathbf{12}, 10, 727, 13] $ .
- Your cow plays against the cow with Cowdeforces rating $ 10 $ and wins. $ a’ = [\mathbf{12}, 727, 13] $ .
- Your cow plays against the cow with Cowdeforces rating $ 727 $ and loses.
In total, your cow wins $ 2 $ matches.
const int N = 2e5+10;
int a[N];
int b[N];
void solve()
{
int n, k;
cin >> n >> k;
int wx = n + 1;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++)
{
if (a[i] > a[k])
{
wx = i;
break;
}
}
int m1 = wx - 2;
swap(a[k], a[wx]);
swap(wx, k);
int ans = 0;
for (int i = 1; i <= n; i++)
{
if (i < k&&a[i]<a[k]) ans = 1;
else if (i > k && a[i] < a[k])
{
ans++;
}
else if (a[i] > a[k]) break;
}
cout << max(ans, m1) << '\n';
}
