一半RE一半WA

GREATchen @ 2023-10-29 16:01:55

#include<iostream>

using namespace std;
 const int N=100000;
    int a[N];

int main()
{
    int count=0;
    int n=0;
    cin>>n;

    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    for(int i=0, j=0;i<n-1;i++)
    {
        while(j>i)
        {
            if(i>j&&a[i]<a[j])
            {
                count++;
            }
            else if(i<j&&a[i]>a[j])
            {
                count++;
            }j++;
        }
    }
    cout<<count;
}

by Syncc @ 2023-10-29 16:16:22

过不了，正解归并或者树状数组

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,mid,a[N],tmp[N];
long long ans=0;
void merge(int left,int right){
    if(left==right){
        return ;
    }
    int mid=(left+right)/2;
    merge(left,mid);
    merge(mid+1,right);
    int i=left,j=mid+1,k=left;
    while(i<=mid && j<=right){
        if(a[i]<=a[j]){
            tmp[k++]=a[i++];
        }else{
            ans+=mid-i+1;
            tmp[k++]=a[j++];
        }
    }
    while(i<=mid){
        tmp[k++]=a[i++];
    }
    while(j<=right){
        tmp[k++]=a[j++];
    }
    for(int i=left;i<=right;i++){
        a[i]=tmp[i];
    }
}
int main()
{
    long long i;
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>a[i];
    }
    merge(1,n);
    cout<<ans<<endl;
    return 0;
}

by do_it_tomorrow @ 2023-10-29 16:18:18

你的数组开小了，开大了之后就不RE了

by do_it_tomorrow @ 2023-10-29 16:18:54

虽然全WA

by do_it_tomorrow @ 2023-10-29 16:22:50

#include<iostream>

using namespace std;
 const int N=10000000;
    int a[N];

int main()
{
    int count=0;
    int n=0;
    cin>>n;

    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    for(int i=0, j=0;i<n-1;i++)
    {
        j=i+1;
        while(j<n)
        {
            if(a[i]>a[j])
            {
                count++;
            }
            j++;
        }
    }
    cout<<count;
}

改成这样之后就只有AC和TLE了，这已经是你的算法的极限了，正解应该是刚才哪位大佬展示的那样

by GREATchen @ 2023-11-03 20:17:40

@Razer_System 感谢感谢