二维偏序(逆序对)

因为风速vf,-w<=vf<=w,因此我们可以算出每一艘船到达原点的时间的取值范围

即取vf=w和vf=-w时,记ai为当vf=w时的用时,记bi为当vf=-w时的用时

所以现在问题转化:为每一元素有两个值ai和bi,求有多少对下标i,j满足a[i]<=a[j]且b[i]>=b[j]

这就是求二维偏序

将每一个元素以a升序为第一关键字,b降序为第二关键字,然后求b的逆序对即可

求逆序对用归并排序

#include <bits/stdc++.h>
using namespace std;
int n,w;
long long ans;
double a[100010],b[100010];
struct node
{
int f,x,v;
double a,b;
}sh[100010];
double m_abs(double x)
{
if (x<0)
return -x;
else
return x;
}
bool cmp(node x,node y)
{
return (x.a<y.a || (x.a==y.a && x.b>y.b));//先排序
}
void m_sort(int l,int r)//归并排序
{
if (l==r)
return;
int mid;
mid=(l+r)/2;
m_sort(l,mid);
m_sort(mid+1,r);
int ll,rr,now;
now=0;
ll=l;
rr=mid+1;
while (ll<=mid && rr<=r)
{
if (a[ll]<a[rr])
{
now++;
b[now]=a[ll];
ll++;
}
else
{
now++;
b[now]=a[rr];
rr++;
ans+=(long long)mid-ll+1;//统计逆序对
}
}
for (int i=ll;i<=mid;i++)
{
now++;
b[now]=a[i];
}
for (int i=rr;i<=r;i++)
{
now++;
b[now]=a[i];
}
for (int i=1;i<=now;i++)
{
a[l+i-1]=b[i];
}
}
int main()
{
scanf("%d%d",&n,&w);
for (int i=1;i<=n;i++)
{
scanf("%d%d",&sh[i].x,&sh[i].v);
if (sh[i].x>0)
sh[i].f=1;
}
for (int i=1;i<=n;i++)//a表示当vf=w时的用时,b表示当vf=-w时的用时
{
if (sh[i].f==0)
{
sh[i].a=m_abs((sh[i].x*1.0)/((sh[i].v+w)*1.0));
sh[i].b=m_abs((sh[i].x*1.0)/((sh[i].v-w)*1.0));
}
else
{
sh[i].b=m_abs((sh[i].x*1.0)/((sh[i].v-w)*1.0));
sh[i].a=m_abs((sh[i].x*1.0)/((sh[i].v+w)*1.0));
}
}
sort(sh+1,sh+1+n,cmp);
for (int i=1;i<=n;i++)
a[i]=sh[i].b;//求b的逆序对
m_sort(1,n);
printf("%lld\n",ans);
}

最新文章

  1. github免输用户名/密码SSH登录的配置
  2. jvm系列(五):tomcat性能调优和性能监控(visualvm)
  3. IBatis 批量插入数据
  4. codeforces 712A. Memory and Crow
  5. Apple Remote Push Notifications
  6. Chrome 插件集锦
  7. spring【一】 学习
  8. Spark Standalone cluster try
  9. java对象深度拷贝
  10. Windows 查看某个端口号是否被占用
  11. Codeforces Gym100783H 最短路 其他
  12. VideoView 监听视频格式不支持时的错误。
  13. eclipse自动添加注释
  14. swift -基础语法
  15. Java基础—线程
  16. ios 查看模拟器路径以及应用的文件夹
  17. rabbitmq学习(五):springboot整合rabbitmq
  18. WIN 10 初体验:期待越多失望越大
  19. [SHOI2010]最小生成树
  20. npm属性笔记

热门文章

  1. Java安全之URLDNS链
  2. CSP-S 2019 游记,以及AFO
  3. CentOS7 没有安装 ifconfig 命令
  4. form中的标签例子
  5. CentOS 7操作系统基础优化介绍
  6. widows安装ffmpeg
  7. nginx安全: 配置http基本验证(Basic Auth)(nginx 1.18.0)
  8. Python函数的定义和参数
  9. C# 面试前的准备_基础知识点的回顾_05
  10. vue学习大纲