[loj 2875]「JOISC 2014 Day1」拉面比较

题目链接

https://loj.ac/problem/2875

题解

Subtask 1

注意到\(n \leq 30\),我们只需两两比较即可。

比较次数的上限为\(n(n-1)/2 \leq 435\),可以通过第一个子任务,期望得分20。

Subtask 2

一个排列中的最大值显然具备这样一个性质:这个最大值一定大于其他任何值。

同理,一个排列中的最小值也都小于其他任何值。

因此我们可以通过\(2(n-1) \leq 598\)次比较来解决第二个子任务:先记录前\(i\)个元素中最大值和最小值的位置。当循环到第\(i+i\)个元素时,只需将当前元素和最大值最小值各比较一次即可。

这样我们就拿到了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);
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注