为什么把 < 改成<=即可 AC?

P1908 逆序对

Hatsunatsu @ 2023-12-23 19:28:30

rt,萌新刚学 OI,如果是 < 的话能拿 30 分,但改成 <= 就 AC 了,求解释。



#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>

using namespace std; 

typedef long long ll;

const int MAXN=1e6+10;
const int MOD=1e9+7;

ll a[MAXN],b[MAXN],ans;

void merge(ll l,ll r){
    ll i,j,k,mid;
    for(k=l;k<=r;++k){
        b[k]=a[k];
    }
    i=l;
    mid=(l+r)/2;
    j=mid+1;
    k=l;
    while(i<=mid&&j<=r){
        if(b[i]<b[j]){  // 如果把这个改成 <= 就 WA 了
            a[k++]=b[i++];
        }
        else{
            a[k++]=b[j++];
            ans+=mid-i+1;
        }
    }
    while(i<=mid){
        a[k++]=b[i++];
    }
    while(j<=r){
        a[k++]=b[j++];
    }
}

void mergeSort(ll l,ll r){
    if(l<r){
        ll mid=(l+r)/2;
        mergeSort(l,mid);
        mergeSort(mid+1,r);
        merge(l,r);
    }
}

int main(){
    ll n;
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    } 
    mergeSort(1LL,n);
    printf("%lld\n",ans);
    return 0;
}

by cff_0102 @ 2023-12-23 19:30:27

如果把这个改成 <= 就 WA 了 => 如果把这个改成 <= 就 AC 了 吧。


by Hatsunatsu @ 2023-12-23 19:31:45

@cff_0102 啊对,脑抽了。


by FiraCode @ 2023-12-23 19:35:44

@Hatsunatsu 假如是 < 的话,那么 a_i =a_j 的情况会算上,就不对了


by Hatsunatsu @ 2023-12-23 19:36:31

@FiraCode 明白了,谢谢~


|