題目：
分析：雖然是之前做過的，雖然是一道經典的題，雖然大標題已經給出了是分治，
但是自己準備開始寫暴力時，才想到了分治哦，
是左邊不斷分治，右邊還要排序嗎？
不是，看到是分治也沒想起來怎么做！
看題解才想到：
左右兩邊都排好了，然后找左邊一個和右邊另一個的逆序對，會嗎？ 會，那就是歸并排序基礎上進行修改，最后終止條件就是只有一個或者兩個元素，
代碼：使用lower_bound()，Tle：
#include<bits/stdc++.h>
using namespace std;
int m;
int A[500005];
int B[500005];
int ans=0;
void f(int x,int y)
{//包括下標為x和下標為y的， 從小到大排序
if(x==y) return;
if(x+1==y)
{
if(A[x]>A[y]) {
ans++; swap(A[x],A[y]);
}
return;
}
int c=(x+y)/2;
f(x,c);
f(c+1,y);
for(int i=x;i<=c;i++)
{
int cc=lower_bound(A+c+1,A+y+1,A[i])-A-c-1;
ans=ans+cc;
}
//合并
int b1=x,b2=c+1;//合并時的兩個指標
int bb=x;
while(1)
{
if(b1==c+1 && b2==y+1) break;
if(b1==c+1)
{
B[bb]=A[b2];bb++;b2++;
}
else if(b2==y+1)
{
B[bb]=A[b1];bb++;b1++;
}
else{
if(A[b1]>A[b2])
{
B[bb]=A[b2];bb++;b2++;
}
else{
B[bb]=A[b1];bb++;b1++;
}
}
}
for(int i=x;i<=y;i++)
{
A[i]=B[i];
}
}
int main()
{
cin>>m;
for(int i=0;i<m;i++) cin>>A[i];
f(0,m-1);
//for(int i=0;i<m;i++) cout<<A[i]<<' ';
//cout<<endl;
cout<<ans;
}應該在歸并合并的時候進行統計：
#include<bits/stdc++.h>
using namespace std;
int m;
int A[500005];
int B[500005];
int ans=0;
void f(int x,int y)
{//包括下標為x和下標為y的， 從小到大排序
if(x==y) return;
if(x+1==y)
{
if(A[x]>A[y]) {
ans++; swap(A[x],A[y]);
}
return;
}
int c=(x+y)/2;
f(x,c);
f(c+1,y);
//合并
int b1=x,b2=c+1;//合并時的兩個指標
int bb=x;
while(1)
{
if(b1==c+1 && b2==y+1) break;
if(b1==c+1)
{
B[bb]=A[b2];bb++;b2++;
//ans=ans+y-c+1;
}
else if(b2==y+1)
{
B[bb]=A[b1];bb++;b1++;
}
else{
if(A[b1]>A[b2])
{
B[bb]=A[b2];bb++;b2++;
ans=ans+c-b1+1;
}
else{
B[bb]=A[b1];bb++;b1++;
}
}
}
for(int i=x;i<=y;i++)
{
A[i]=B[i];
}
}
int main()
{
cin>>m;
for(int i=0;i<m;i++) cin>>A[i];
f(0,m-1);
//for(int i=0;i<m;i++) cout<<A[i]<<' ';
//cout<<endl;
cout<<ans;
}轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/26442.html
標籤：其他
上一篇：計算機網路第一章考研題