Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

题意解析 + 两种解法(归并排序 + BIT)

Posted by 947186602 at 2020-09-17 11:16:49 on Problem 3067
/**
一个类二分图,一边有N个城市,一边有M个城市,现在在这两类城市中连线,请你计算这些线几个交点?(每条跟其他同一条线相交只有一个交点)
M <= 1000, N <= 1000
思路:
对Ax,Ay和Bx,By两条高速公路,有相交点必须(Ax-Bx)*(Ay-By)<0,即求逆序对数量,朴素的求法是n^2 ,这里估计不行,因为边最多10W条
先按照x从小到大排序,然后再求y中的逆序对即可。因为同一个城市是不算的如:4,1和4,2不相交,不能4,2排前 4,1排后
所以x排序时只要相同的把y较小的放到前面即可,这样后面求逆序对时就不会算进去了。
(排序是为了更好算逆序数,固定住x,求y的逆序对,并不是说排了序就没有逆序对了,只是排序后无需考虑x只需看y)

求逆序对的方法有两种,一种是基本BIT求法,
另一种是归并排序的扩展应用:求逆序对

该题逆序对数量很大,需要long long

这里用的归并排序求法 or 熟悉的BIT算法

Sample Input
1
3 4 4
1 4
2 3
3 2
3 1
Sample Output
Test case 1: 5

**/
#include<cstdio>
#include<string.h>
#include<algorithm>
using namespace std;
struct Node
{
    int x,y;
    bool operator < (const Node& a) const
    {
        if(a.x == x)
            return y < a.y;
        else return x < a.x;
    }
} node[1005 * 1005];
int a[1005 * 1005],c[1005 * 1005]; // K的范围
int N,M,K,T;
long long cnt; //

void merge_sort(int x[],int left,int right,int y[])
{
    if(left < right) //大于等于不用管
    {
        int mid = left + (right - left) / 2;//好习惯,防溢出
        //先对左右归并排序
        merge_sort(x,left,mid,y);
        merge_sort(x,mid+1,right,y);

        //此时左右都已经排好序了,归并开销
        int i = left,j = mid + 1,k = left;//左起点,右起点,临时存储起点
        while(i <= mid && j <= right)
        {
            if(x[i] <= x[j])
            {
                y[k++] = x[i++];
            }
            else
            {
                y[k++] = x[j++];
                cnt += mid - i + 1;//记录逆序对,相当于对右边每个值,计算左边有多少比它大的
            }
        }
        //补上剩下的
        while(i <= mid)
            y[k++] = x[i++];
        while(j <= right)
            y[k++] = x[j++];
        //临时工转正
        for(i = left ; i <= right; i++)
        {
            x[i] = y[i];
        }
    }
}

void solve_by_sort() //454MS
{
    for(int i = 0; i < K; ++i)
    {
        a[i] = node[i].y; //给归并的数组赋值
    }
    cnt = 0;// 重置逆序对数
    merge_sort(a,0,K-1,c);
}

int BIT[1005 << 1];
void add(int n,int v){ //单点更新
     while(n < 1005){
          BIT[n] += v;
          n += n&-n;
     }
}

int sum(int n){  //区域求和
     int res = 0;
     while(n > 0){
          res += BIT[n];
          n -= n&-n;
     }
     return res;
}

void solve_by_BIT(){  //391MS
     memset(BIT,0,sizeof(BIT));
     cnt = 0;
     for(int i = 0;i < K;++i){
          cnt += i - sum(node[i].y); //加上j < i 的且aj > ai  sum(node[i].y) 代表j < i 且 aj <= ai 的数量
          add(node[i].y,1);
     }
}

int main()
{
    scanf("%d",&T);
    for(int j = 1; j <= T; ++j)
    {
        scanf("%d%d%d",&N,&M,&K);
        for(int i = 0; i < K; ++i)
        {
            scanf("%d%d",&node[i].x,&node[i].y);
        }
        sort(node,node+K);
        //解法任选1种
        //solve_by_sort(); 
        solve_by_BIT();
        printf("Test case %d: %lld\n",j,cnt);
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator