校门里的树（Mix Version）题解

2simon2008 · 2021-05-25 17:29:40 · 个人记录

题目

题目链接

题意简化：

求第p+1大数，第q+1小数。

思路&&代码

20pts

直接求最大最小数，用max、min函数，时间复杂度O(n)

60pts

运用排序sort函数，再输出，时间复杂度O(nlogn)

题目：Easy Version

#include <bits/stdc++.h>
using namespace std;
int n,p,q,a[500005];
int main()
{
  scanf("%d%d%d",&n,&p,&q);
  for(int i=1; i<=n; i++) scanf("%d",&a[i]);//输入
  sort(a+1,a+n+1);//排序
  printf("%d\n%d\n",a[n-p],a[q+1]);//输出
  return 0;
}

另外40pts

最大值只取前p+1，最小值只取前q+1个保存即可，每次更新，时间复杂度O(np)

p.s. 这个算法只适用于60pts，因为他的maxn和minn数组只有10……会RE。

题目：Hard Version。

#include <bits/stdc++.h>
using namespace std;
int n,p,q,x,maxn[11],minn[11];
int main()
{
  scanf("%d%d%d",&n,&p,&q);
  memset(minn,0x3f,sizeof(minn));
  for(int i=1; i<=n; i++)
  {
    scanf("%d",&x);
    for(int j=1; j<=p+1; j++)
      if(maxn[j]<x)
      {
        for(int k=p+1; k>j; k--)
          maxn[k]=maxn[k-1];
        maxn[j]=x;
        break;
      }
    for(int j=1; j<=q+1; j++)
      if(minn[j]>x)
      {
        for(int k=q+1; k>j; k--)
          minn[k]=minn[k-1];
        minn[j]=x;
        break;
      }
  }
  printf("%d\n%d\n",maxn[p+1],minn[q+1]);
  return 0;
}

100pts

混合一下,分类讨论可以得到一百分

using namespace std;
int n,p,q,x,maxn[11],minn[11],a[550005];
int main()
{
  freopen("9.in","r",stdin);
  freopen("9.out","w",stdout);
  scanf("%d%d%d",&n,&p,&q);
  memset(minn,0x3f,sizeof(minn));
  if(n>5e5)
  {
    for(int i=1; i<=n; i++)
    {
      scanf("%d",&x);
      for(int j=1; j<=p+1; j++)
        if(maxn[j]<x)
        {
          for(int k=p+1; k>j; k--)
            maxn[k]=maxn[k-1];
          maxn[j]=x;
          break;
        }
      for(int j=1; j<=q+1; j++)
        if(minn[j]>x)
        {
          for(int k=q+1; k>j; k--)
            minn[k]=minn[k-1];
          minn[j]=x;
          break;
        }
    }
    printf("%d\n%d\n",maxn[p+1],minn[q+1]);
  }
  else
  {
    for(int i=1; i<=n; i++) scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    printf("%d\n%d\n",a[n-p],a[q+1]);
  }
  return 0;
}

总结

再次链接Easy Version和Hard Version。

这道其实有点偏思路，但还是不出普及组第“2.5”题的范围

完结撒花！

校门里的树（Mix Version） 题解

题目