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 假如是 <
的话,那么
by Hatsunatsu @ 2023-12-23 19:36:31
@FiraCode 明白了,谢谢~