2 条题解

  • 0
    @ 2025-10-8 16:56:23
    #include<bits/stdc++.h>
    using namespace std;
    const int N=1e5+10;
    int n,a[N],h[N],c[N];
    void add(int x,int k){for(;x<=n;x+=x&-x)c[x]+=k;}
    int sum(int x){int s=0;for(;x;x-=x&-x)s+=c[x];return s;}
    int main()
    {
        scanf("%d",&n);
        for(int i=2;i<=n;i++)scanf("%d",&a[i]);
        memset(c,0,sizeof(c));
        for(int i=1;i<=n;i++)add(i,1);
        for(int i=n;i>=1;i--)
    	{
            int l=1,r=n,t=0;//t=0以防找不到mid 
            while(l<=r)
    		{
                int mid=(l+r)>>1;
                if(sum(mid)<a[i]+1)l=mid+1,t=mid;
                else r=mid-1;
            }
            add(h[i]=t+1,-1);
        }
        for(int i=1;i<=n;i++)printf("%d\n",h[i]);
        return 0;
    }
    
    • 0
      @ 2025-10-8 16:56:16
      #include<bits/stdc++.h>
      using namespace std;
      const int N=1e5+10;
      int n,a[N],h[N],c[N];
      void add(int x,int k){for(;x<=n;x+=x&-x)c[x]+=k;}
      int sum(int x){int s=0;for(;x;x-=x&-x)s+=c[x];return s;}
      int main()
      {
          scanf("%d",&n);
          for(int i=2;i<=n;i++)scanf("%d",&a[i]);
          memset(c,0,sizeof(c));
          for(int i=1;i<=n;i++)add(i,1);
          for(int i=n;i>=1;i--)
      	{
              int l=1,r=n,t=0;//t=0以防找不到mid 
              while(l<=r)
      		{
                  int mid=(l+r)>>1;
                  if(sum(mid)<a[i]+1)l=mid+1,t=mid;
                  else r=mid-1;
              }
              add(h[i]=t+1,-1);
          }
          for(int i=1;i<=n;i++)printf("%d\n",h[i]);
          return 0;
      }
      • 1

      *【树状数组】还原牛序列[USACO03Open] Lost Cows

      信息

      ID
      1326
      时间
      1000ms
      内存
      64MiB
      难度
      5
      标签
      递交数
      80
      已通过
      33
      上传者