25分, 其他TLE

Andy_hpy @ 2024-10-06 12:13:52

#include <bits/stdc++.h>
#include <unistd.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ldb;
const ll MAXN=5*1e5+5;
ll n,ans,a[MAXN];
int main() {
    scanf("%lld",&n);
    for(ll i=0;i<n;++i)scanf("%lld",a+i);
    for(ll i=0;i<n-1;++i){
        for(ll j=i+1;j<n;++j){
            if(a[i]>a[j])++ans;
        }
    }
    printf("%lld\n",ans);
    return 0;
}

by kaiweiwang @ 2024-10-06 12:21:43

在归并排序上稍加改动就行了

#include <cstdio>
int a[500005];
int T[500005];
long long ans;
void Merge(int data[], int l, int r)
{

    int mid = (l + r)/2;
    int i = l;
    int j = mid+1;

    int d = l;
    while(i <= mid&&j <= r)
    {
        if(a[i] <= a[j])
        {
            T[d++] = a[i++];
        }else
        {
            T[d++] = a[j++];
            ans+=mid-i+1;
        }
    }
    while(i <= mid)
    {
        T[d++] = a[i++];
    }
    while(j <= r)
    {
        T[d++] = a[j++];
    }
    for(int i = l; i <= r; i++)a[i] = T[i];
}
void Mergesort(int data[], int l, int r)
{
    if(l < r)
    {
        int mid =(l+r)/2;
        Mergesort(data, l,mid);
        Mergesort(data, mid+1,r);
        Merge(data,l,r);
    }
}
int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)scanf("%d", &a[i]);
    Mergesort(a,1,n);
    printf("%lld",ans);
}

求关

by dongzirui0817 @ 2024-10-06 12:38:24

@Andy_hpy 你这暴力，不 T 才怪

by Andy_hpy @ 2024-10-06 12:55:57

@kaiweiwang 为什么是ans+=mid-i+1

by Ace2012 @ 2024-10-10 08:36:04

你觉得这种方法能过的题能算黄题吗

by Ace2012 @ 2024-10-10 08:37:55

by Andy_hpy @ 2024-10-13 15:17:42

@Ace2012 也是, 这样绝对不能算黄题

by Andy_hpy @ 2024-10-13 15:18:07

@Ace2012 哦, 是这样啊, 懂了