还有什么类型的网站,台州网站建设推广,青海省网站建设平台,最好的赣州网站建设Inverse Pair
题意#xff1a;
一个数组a#xff0c;现在构造一个数组c#xff0c;c[i]a[i]0/1#xff08;0或1#xff09;#xff0c;使得c的逆序对最少
题解#xff1a;
如果x在x1的后面#xff0c;我们让x这个数1,x1不变#xff0c;就可以让逆序对少1。如果x在…Inverse Pair
题意
一个数组a现在构造一个数组cc[i]a[i]0/10或1使得c的逆序对最少
题解
如果x在x1的后面我们让x这个数1,x1不变就可以让逆序对少1。如果x在x1后面我们就认为连边(x1,x),x也有可能与x-1连边形成一个长度为L的链那减少的逆序对数量就是L/2
代码
//还是自己菜最后还是看了网上模板才写出来的#include bits/stdc.h#define LL long long
using namespace std;const int N3e610;
LL num[N],a[N];
LL ans;
void Merge(int l,int mid,int r) //分治的治 合并是求逆序对的关键
{int il,jmid1,kl;while(imidjr){if(num[i]num[j]) //前半部分中比num[i]大的数都比num[j]大将num[j]放在num[i]前面的话逆序数要加上mid1-i{a[k]num[j];ansmid-i1; //统计逆序对}else //这里这情况不产生逆序对a[k]num[i];}while(imid)a[k]num[i];while(jr)a[k]num[j];for(int el;er;e) //将这次操作完的num数组更新num[e]a[e];
}void Merge_sort(int l,int r) //分治的分 在这里不断地把一个串细分然后回溯合并
{if(lr){int mid(lr)/2;Merge_sort(l,mid);Merge_sort(mid1,r);Merge(l,mid,r);}
}
int vis[N];
int main()
{int n;cinn;int tot0;for(int i0;in;i){cinnum[i];if(vis[num[i]1]){tot;}else vis[num[i]]1;}ans0;Merge_sort(0,n-1); //coutansendl;coutans-tot;return 0;
}
/*
8
8 1 6 3 4 5 2 7
*/
