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