目录
显示
题目链接
题解
Subtask 1
注意到 \(n \leq 30\)，我们只需两两比较即可。
比较次数的上限为 \(n(n-1)/2 \leq 435\)，可以通过第一个子任务，期望得分 20。
Subtask 2
一个排列中的最大值显然具备这样一个性质：这个最大值一定大于其他任何值。
同理，一个排列中的最小值也都小于其他任何值。
因此我们可以通过 \(2(n-1) \leq 598\) 次比较来解决第二个子任务：先记录前 \(i\) 个元素中最大值和最小值的位置。当循环到第 \(i+1\) 个元素时，只需将当前元素和最大值最小值各比较一次即可。
这样我们就拿到了 50 分。
Subtask 3
怎样进一步优化比较次数呢？
让我们继续从最大值和最小值的性质入手：设当前处理到的数为 \(a_i\)，显然假如存在一个数比 \(a_i\) 大， \(a_i\) 就不可能成为最大值；同理，假如存在一个数比 \(a_i\) 小，\(a_i\) 就不可能成为最小值。
仿照电子竞技中的胜者组和败者组的思路，我们首先将所有元素按两个一组进行一次比较（特别地，假如元素个数为奇数，最后一个元素就要轮空）。
比较后所有较大的元素都具有了竞争最大值的资格，所有较小的元素也都具有了竞争最小值的资格。
接下来采用 Subtask 2 的方法，在较大元素中确定最大值，较小元素中确定最小值即可。
最多需要比较多少次呢？首先分组过程的比较次数是 \(\left \lfloor n/2 \right \rfloor\)（可能会有一个元素轮空），决出最大值和最小值各需要 \(\left \lceil n/2 \right \rceil -1\)，因此比较次数为 \(\left \lceil 3n/2 \right \rceil -2 \leq 598\)。
#include "ramen.h"
void Ramen(int n)
{
int maxa=0,mina=0;
for(int i=1;i<n-1;i+=2)
if(Compare(i,i+1)==1)
{
if(Compare(i,maxa)==1)maxa=i;
if(Compare(i+1,mina)==-1)mina=i+1;
}
else
{
if(Compare(i+1,maxa)==1)maxa=i+1;
if(Compare(i,mina)==-1)mina=i;
}
if(n%2==0)
{
if(Compare(n-1,maxa)==1)maxa=n-1;
else if(Compare(n-1,mina)==-1)mina=n-1;
}
Answer(mina,maxa);
}