题解：SP4226 MSE06H - Japan

· · 题解

题解：SP4226 MSE06H - Japan

题目传送门。

题意：

左侧从上往下有 N 个节点，右侧从上往下有 M 个节点，之间有 k 条边，问边与边之间有多少个交点。

分析

在样例中 n=3,m=4 那么东海岸，西海岸就如图所示：

题目让我们求其连线的交点个数，那我们只要知道在什么情况下，两线相交就可以了。

如图：

我们可以看出来，在 x_1<x_2 和 y_2>y_1 的情况下，两线相交。

思路：

定睛一看，这不就是逆序对吗。这时，思路就非常清晰了。

于是，我们就切了一道水题。

警示后人

多测要清空。

范围看仔细。

输出要注意。

（居然押韵了）

代码：

抄代码可不是好孩子哦！

#include<bits/stdc++.h>
#define int long long // 好习惯 
using namespace std;
const int N=1000001;
struct node{
    int x,y;
};
int T,n,m,k,tr[N];
node c[N];
int lowbit(int x){
    return (-x)&x;
}
void add(int x){
    while(x<=1001){ // n,m均小于等于1000 
        tr[x]++; // 直接加一 
        x+=lowbit(x);
    } 
}
int ask(int x){
    int ans=0;
    while(x){
        ans+=tr[x];
        x-=lowbit(x);
    }
    return ans;
}
bool cmp(node a,node b){
    return a.x<b.x||(a.x==b.x&&a.y<b.y); //  条件写清楚 
}
signed main(){
    scanf("%lld",&T);
    for(int o=1;o<=T;o++){
        memset(c,0,sizeof(c)); // 要清空！！！ 
        memset(tr,0,sizeof(tr)); // 要清空！！！ 
        scanf("%lld%lld%lld",&n,&m,&k);
        for(int i=1;i<=k;i++){
            scanf("%lld%lld",&c[i].x,&c[i].y);
        }
        sort(c+1,c+1+k,cmp);
        int ans=0;
        for(int i=1;i<=k;i++){
            ans+=i-1-ask(c[i].y); // 要倒过来 
            add(c[i].y);
        }
        printf("Test case %lld: %lld\n",o,ans); // 输出要注意 
    }
    return 0; // 好习惯 
}