比赛 |
防止浮躁的小练习v0.5 |
评测结果 |
AAAAAAAAWW |
题目名称 |
罗伊德的防晒霜 |
最终得分 |
80 |
用户昵称 |
dududu |
运行时间 |
0.377 s |
代码语言 |
C++ |
内存使用 |
0.73 MiB |
提交时间 |
2016-10-15 18:34:02 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define lcy 19283746
#define KN 100010
struct Point
{
int x,y;
Point(){
x=y=0;
}
};
int N;
Point p[KN];
int merge_tmp[KN];
bool my_cmp(const Point &tmpa,const Point &tmpb)
{
return tmpa.x<tmpb.x;
}
void init()
{
cin>>N;
for(int i=1,tmpx,tmpy;i<=N;i++)
{
scanf("%d %d",&p[i].x,&p[i].y);
}
sort(p+1,p+1+N,my_cmp);
}
int merge_sort(int l,int mid,int r)//对y排序 x方向上交换距离和即为最少交换次数
{
if(l>=r) return 0;//边界
int ans=merge_sort(l,l+(mid-l)/2,mid)+merge_sort(mid+1,mid+(r-mid)/2,r);//首先对[l,mid],[mid+1,r]排序
//假装我们已经把 [l,mid],[mid+1,r]排序好的样子
int i=l,j=mid+1,cur=l;//i为[l,mid]的指针(口胡),j同理,cur为临时数组的*...
while(i<=mid&&j<=r)
{
if(p[i].y>p[j].y) merge_tmp[cur++]=p[j++].y,ans+=mid-i+1;//需要交换
else merge_tmp[cur++]=p[i++].y;//不需要交换
while(ans>=lcy) ans-=lcy;//%lcy
}
//临时数组中可能有未交换的
while(i<=mid) merge_tmp[cur++]=p[i++].y;
while(j<=r) merge_tmp[cur++]=p[j++].y;
for(i=l;i<=r;i++) p[i].y=merge_tmp[i];//复制数组
return ans;
}
int main()
{
freopen("EOADtulad.in","r",stdin);
freopen("EOADtulad.out","w",stdout);
init();
printf("%d",merge_sort(1,N/2,N));
return 0;
}