2 条题解

  • 0
    @ 2025-2-27 21:55:02
    #include <bits/stdc++.h>
    
    using namespace std;
    
    int main()
    {
    int n;
    cin>>n;
    vector<int> a;
    for(int i = 0;i<n;i++)
    {
      int t ;
      cin>>t;
      a.push_back(t);
    }
    sort(a.begin(),a.end());
    for(int i = 0;i<n;i++)
    {
      if(i == n-1)
      cout<<a[i];
      else 
      cout << a[i]<<" ";
    }
      return 0;
    }
    
    • 0
      @ 2025-1-16 17:50:53

      给大家分享一下归并排序的思路。

      思路

      归并排序是什么?分裂+合并。

      首先把数组 aa 平分成两半。

      如可以把 (3,2,1,7,5,6,4,8)(3,2,1,7,5,6,4,8) 分成 (3,2,1,7)(3,2,1,7)(5,6,4,8)(5,6,4,8)

      然后把 (3,2,1,7)(3,2,1,7) 分成 (3,2)(3,2)(1,7)(1,7)

      接着把 (3,2)(3,2) 分成 (3)(3)(2)(2)

      显然不能继续分下去,那就合并。

      首先把首元素更小的 (2)(2) 的数组的首元素提取出来,变成空数组后,也只能把 (3)(3) 加入。得到了 (2,3)(2,3)

      然后以此类推,(3,2,1,7)(3,2,1,7) 变成了 (1,2,3,7)(1,2,3,7)(5,6,4,8)(5,6,4,8) 变成了 (4,5,6,8)(4,5,6,8),最后合并这两个子数组,首元素比较,合并顺序为 lllrrrlr\text {lllrrrlr}ll 表示提取 (1,2,3,7)(1,2,3,7)rr 表示提取 (4,5,6,8)(4,5,6,8))。

      显然,归并排序运用了递归和分治的思想。

      代码

      #include <bits/stdc++.h>
      using namespace std;
      int n,a[100005],w[100005];
      void merge(int l,int r){
          if (l==r)
              return ;
          int mid=(l+r)>>1;
          merge(l,mid);
          merge(mid+1,r);
          int i=l,j=mid+1,cnt=l;
          while (i<=mid&&j<=r)
              if (a[i]<=a[j])
                  w[cnt++]=a[i++];
              else
                  w[cnt++]=a[j++];
          while (i<=mid)
              w[cnt++]=a[i++];
          while (j<=r)
              w[cnt++]=a[j++];
          for (int k=l;k<=r;k++)
              a[k]=w[k];
      }
      int main(){
          cin>>n;
          for (int i=1;i<=n;i++)
              cin>>a[i];
          merge(1,n);
          for (int i=1;i<=n;i++)
              cout<<a[i]<<" ";
          return 0;
      }
      
      
      • 1

      信息

      ID
      5235
      时间
      1000ms
      内存
      256MiB
      难度
      2
      标签
      递交数
      389
      已通过
      118
      上传者