为什么把 < 改成<=即可 AC?
  • 板块P1908 逆序对
  • 楼主Hatsunatsu
  • 当前回复4
  • 已保存回复5
  • 发布时间2023/12/23 19:28
  • 上次更新2023/12/23 21:45:25
查看原帖
为什么把 < 改成<=即可 AC?
1079073
Hatsunatsu楼主2023/12/23 19:28

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;
}
2023/12/23 19:28
加载中...