欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

分治 归并排序和逆序对

程序员文章站 2022-05-10 16:11:45
...

板子传送门

对于归并排序,是一种O(n*logn)的一种排序方法,然后归并排序中没有一出现,全部都是l因为他的出发点不一定是 1(当排序右边的时候),对于该次所排序的左右区间,在左右区间的两端的元素分别有序,因为是用的递归,所以是从小区间往大区间来排序的,所以该区间分成的两个区间是一定有序的。

#include<bits/stdc++.h>
using namespace std;
int a[1000],temp[1000];

void midsort(int l,int r)
{
    if(l==r)
        return ;
    int mid=l+r>>1;
    midsort(l,mid);    //该处是从l到mid,因为处理右端时开始的端点不是1
    midsort(mid+1, r);
    int i=l,j=mid+1,k=l;    //该处的k同理上面的l
        while(i<=mid&&j<=r)
        {
            if(a[i]<a[j])
                temp[k++]=a[i++];
            else
                temp[k++]=a[j++];
        }
    while(i<=mid) temp[k++]=a[i++];    //处理剩下的
    while(j<=r) temp[k++]=a[j++];
    for(int i=l;i<=r;i++)
        a[i]=temp[i];
    return ;
}

int main()
{
    std::ios::sync_with_stdio(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    midsort(1,n);
    for(int i=1;i<n;i++)
        cout<<a[i]<<" ";
    cout<<a[n]<<endl;
    return 0;
}

逆序对

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[1000],temp[1000];

ll midsort(int l,int r)
{
    if(l==r)
        return 0;
    int mid=l+r>>1;
    ll ans=midsort(l,mid)+ midsort(mid+1, r);
    int i=l,j=mid+1,k=l;
     while(i<=mid&&j<=r)
        {
            if(a[i]<a[j])
                temp[k++]=a[i++];
            else
            {
                ans+=mid-i+1;
                temp[k++]=a[j++];
            }
        }
    while(i<=mid) temp[k++]=a[i++];
    while(j<=r) temp[k++]=a[j++];         //最后的这一个部分不只是合并最后没走完的数,而且还要合并答案,该处不合并是因为当j有剩余的时候,i已经走到了mid+1,此时根据表达式不更新答案
    for(int i=l;i<=r;i++)
        a[i]=temp[i];
    return ;
}

int main()
{
    std::ios::sync_with_stdio(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    midsort(1,n);
    for(int i=1;i<n;i++)
        cout<<a[i]<<" ";
    cout<<a[n]<<endl;
    return 0;
}

附上一个更新答案的题目

#include<bits/stdc++.h>
using namespace std;
#define ll  long long
#define std std::ios::sync_with_stdio(0)
#define mem(a,b) memset(a,b,sizeof(a));
const int INF = 0x3f3f3f3f;

void read(ll& x)
{
	ll f = 1;         //f为符号位
	x = 0;
	char s = getchar();          //读入一个字符
	while (s > '9' || s < '0')      //处理空格。换行什么的,并且读入符号
	{
		if (s == '-')
			f = -1;
		s = getchar();
	}
	while (s >= '0' && s <= '9')     //不断地读入数字字符来计算得到数字
	{
		x = x * 10 + s - '0';
		s = getchar();
	}
	x *= f;               //乘以符号即可得到数字
}

const int maxn = 5e4 + 10;
struct vx
{
	ll v, x;
}a[maxn],temp[maxn];
ll sum[maxn];

ll solve(int l, int r)
{
	if (l == r)
		return 0;
	int mid = l + r >> 1;
	ll ans = solve(l, mid) + solve(mid + 1, r);
	
	sum[l - 1] = 0;

	int i = l, j = mid + 1;

	for (; i <= mid; i++)
		sum[i] = sum[i - 1] + a[i].x;
	i = l, j = mid + 1;
	int k = l;
	while (i <= mid&&j <= r)
	{
		if (a[i].x <a[j].x)
			temp[k++] = a[i++];
		else
		{
			ans += a[j].v * (a[j].x * (i - l) - sum[i - 1] + sum[mid] - sum[i - 1] - a[j].x * (mid - i + 1));
			temp[k++] = a[j++];
		}
	}
	while (i <= mid)
		temp[k++] = a[i++];
	while (j <= r)
	{
		ans += a[j].v * (a[j].x * (i - l) - sum[mid]);
		temp[k++] = a[j++];
	}
	for (i = l; i <= r; i++)
		a[i] = temp[i];
	return ans;
}


int cmp(vx& a, vx& b)
{
	return a.v < b.v;
}
int main()
{
	int n;
	std;
	cin >> n;

	for (int i = 1; i <= n; i++)
		read(a[i].v), read(a[i].x);

	sort(a + 1, a + n + 1, cmp);

	ll ans = solve(1, n);

	cout << ans << '\n';
	return 0;
}

对于该题的表达式有max(a,b)取大值的情况,我们选择直接对该元素进行排序然后就可以化简表达式,然后对于算答案贡献的时候,我一开始的思路是直接强行枚举的,找到第一个左区间的x是大于右区间的时候,利用前缀和进行处理,但是会TLE,而联想到归并排序的时候,也是会处理一个大小于的情况,所以选择使用归并排序来对x进行排序的同时更新答案。

相关标签: 分治 算法