【洛谷P1367】蚂蚁
2024-09-26 17:02:33
蚂蚁
【题目描述】
在一根无限长的木棍上,用n只蚂蚁,每只蚂蚁有一个初始位置和初始朝向,蚂蚁们以每秒一个单位的速度向前移动,当两只蚂蚁相遇时,它们会掉头(掉头时间忽略不计)。现给出每只蚂蚁的初始位置和初始朝向,请你计算出它们在t秒后的位置和朝向。
思路:
1.对于每只蚂蚁,它的坐标在所有蚂蚁中的次序无论怎样移动都不会改变。(因为当两只蚂蚁相遇时,它们会掉头)
2.对于两只蚂蚁同时掉头,可以看作“两只蚂蚁交换编号”,继续向前移动,所以O(logn)的时间(排序)就可以算出最终在一个确定的位置有一个不确定编号的蚂蚁朝着一个确定的方向,求出每只蚂蚁的编号,可利用性质1
sort是个好东西。。
贴代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,t;
struct ant{
int data; //记录初始位置
int xb; //记录蚂蚁编号
int fx; //记录方向
int ans; //记录最终位置
} a[];
struct aaa{
int data;
int fx;
} b[]; //用于计算最终位置并按坐标大小排序,对应到a数组
bool cmp1(ant x,ant y)
{
return x.data<y.data;
}
bool cmp2(aaa x,aaa y)
{
return x.data<y.data;
}
bool cmp3(ant x,ant y)
{
return x.xb<y.xb;
}
int main()
{
scanf("%d%d",&n,&t);
for(int i=;i<=n;i++)
{
scanf("%d%d",&a[i].data,&a[i].fx);
a[i].xb=i;
}
sort(a+,a++n,cmp1); //按坐标大小排序
for(int i=;i<=n;i++)
{
b[i].data=a[i].fx==?a[i].data+t:a[i].data-t;
b[i].fx=a[i].fx;
}
sort(b+,b++n,cmp2); //按坐标大小排序
for(int i=;i<=n;i++) //每只蚂蚁移动前后坐标次序不变
{
a[i].ans=b[i].data;
a[i].fx=b[i].fx;
}
for(int i=;i<n;i++)
if(a[i].ans==a[i+].ans) a[i].fx=a[i+].fx=; //若恰好正在转身,输出0
sort(a+,a++n,cmp3);
for(int i=;i<=n;i++)
printf("%d %d\n",a[i].ans,a[i].fx);
return ;
}
最新文章
- js中object类型模拟java中的map
- 30天轻松学习javaweb_Range实现断点续传
- [CF]codeforces round 369(div2)
- world符号大全
- [BZOJ 3888] [Usaco2015 Jan] Stampede 【线段树】
- 排序算法c语言描述---堆排序
- 入门git
- 微机原理基础(五)—— MSP430
- tar解压指定文件
- cf1153E 二分思维交互
- cf1107d 映射关系
- [LeetCode] 90.Subsets II tag: backtracking
- angular模拟web API
- 图片人脸检测——OpenCV版(二)
- Tensorflow[源码安装时bazel行为解析]
- DX9 空间坐标变换示例代码
- 黄聪:C#如何使用fiddlercoreCapture监控手机APP
- uiautomator2.0的配置的两种方法
- Python学习笔记_05:使用Flask+MySQL实现用户登陆注册以及增删查改操作
- Ocelot 配置初始