题目链接http://codeforces.com/problemset/problem/589/D

题目大意:给出n个人行走的开始时刻,开始时间和结束时间,求每个人分别能跟多少人相遇打招呼(每两人只能打招呼一次)。

例:

输入:
3
1 1 10
5 8 2
9 9 10

输出:

2 1 1

解题思路:先按行走的开始时刻排下序,然后直接模拟判断和比他后出现的人是否可以相遇。

第一步判断前面那个人在未走完前,下一人会出现,若不出现,直接break。然后就计算当下一个人出现的时刻,前一个人的位置,然后又分种情况,两个人可能刚好在一起,有可能在他左边,也可能在他右边。刚好在一起很好,直接相遇了,若不相遇,则要判断他们是否同向,若同向,肯定不可能相遇,速度是相同的,判断是否同向,直接两个人的终点减去起点相乘是否大于0就可以,不过要注意的是:他们相乘会爆int,我就因为这个找了一个多小时才找出来,还总以为自己漏了情况。。。。反方向的话,直接计算他们的位置判断是否在他们行走的范围以内即可。

附上代码:

 #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
struct node{
int t; //开始行走的时刻
int s; //开始位置
int f; //结束位置
int id; //序号
}p[];
int n,cnt[];
bool comp(const node &a,const node &b)
{
return a.t<b.t;
} int main()
{
while(scanf("%d",&n)!=EOF)
{
memset(cnt,,sizeof(cnt));
for(int i=;i<n;i++)
{
scanf("%d%d%d",&p[i].t,&p[i].s,&p[i].f);
p[i].id=i;
}
sort(p,p+n,comp); //按开始行走的时刻排序
//cout<<endl;
//for(int i=0;i<n;i++)
// cout<<p[i].t<<" "<<p[i].s<<" "<<p[i].f<<endl;
int t,pos;
for(int i=;i<n-;i++)
{
for(int j=i+;j<n;j++)
{
if(p[i].t+abs(p[i].f-p[i].s)<p[j].t) //第i个人走完了,第j个人还未出现,直接break
break;
t=p[j].t-p[i].t;
if(p[i].f>p[i].s)
pos=p[i].s+t;
else
pos=p[i].s-t; //pos为第j个人出现的时候第i个人的位置
//cout<<pos<<endl;
if(pos==p[j].s) //在j的其实位置相遇
{
cnt[p[i].id]++;
cnt[p[j].id]++;
}
else if(pos<p[j].s)
{
ll y=(ll)(p[i].f-p[i].s)*(ll)(p[j].f-p[j].s);
if(y>) //两个人同向,速度相同,追不上
continue;
if((p[i].f-p[i].s)<&&(p[j].f-p[j].s)>) //反向但是位置不对
continue;
double x=pos+(p[j].s-pos)/2.0; //相遇位置
if(x<=p[i].f&&x>=p[j].f)
{
cnt[p[i].id]++;
cnt[p[j].id]++;
//cout<<p[i].id<<" "<<p[j].id<<endl;
}
}
else
{
ll y=(ll)(p[i].f-p[i].s)*(ll)(p[j].f-p[j].s);
if(y>)
continue;
if((p[i].f-p[i].s)>&&(p[j].f-p[j].s)<)
continue;
double x=pos-(pos-p[j].s)/2.0;
if(x<=p[j].f&&x>=p[i].f)
{
cnt[p[i].id]++;
cnt[p[j].id]++;
//cout<<p[i].id<<" "<<p[j].id<<endl;
}
} }
}
printf("%d",cnt[]);
for(int i=;i<n;i++)
printf(" %d",cnt[i]);
printf("\n");
}
return ;
}

最新文章

  1. STM32 flash 内存分布介绍
  2. 安装opencv以及遇到的坑
  3. .NET平台下,关于数据持久层框架
  4. ContextLoaderListener初始化的前后文和DispatcherServlet初始化的上下文关系
  5. 将非常规Json字符串转换为常用的json对象
  6. Python项目,VS Code控制台输出乱码问题解决办法
  7. Python mysql-python及pycurl使用一例
  8. 顺序栈代码实现&amp;&amp;stack库
  9. SpringBoot自动配置源码调试
  10. spark 2.3 导致driver OOM的一个SparkPlanGraphWrapper源码的bug
  11. windows系统下简单nodejs安装及环境配置
  12. win10 HTTP 错误 500.21 - Internal Server Error
  13. nginx 部署web页面问题
  14. topcoder srm 695 div1 -3
  15. vue-9-动画
  16. 管理git生成的多个ssh key
  17. P3707 [SDOI2017]相关分析
  18. 160420、zTree获取所有选中节点数据
  19. IIS7.5 错误代码0x8007007e HTTP 错误 500.19
  20. 基于mysql的全文索引

热门文章

  1. ps命令
  2. Linux socket多进程服务器框架一
  3. STL之分配器allocator
  4. [redis] 普通 RedisPool 的 CRUD 实现
  5. [AHOI 2006][BZOJ 1269]文本编辑器editor
  6. Lightmapping
  7. 视频: 千重浪Linux系统调试技术培训 03-01_Basic-CPU-Register
  8. Android 字体颜色在一些机型上不适配(textcolor失效)
  9. JAVA 修改 JSESSIONID
  10. sqlite3编译与查询
  11. LR错误整理
  12. spring javaconfig druidsource
  13. maven打包额外的资源文件
  14. 《笨方法学Python》加分题16
  15. angular 4 开发环境下打包文件过大
  16. vsCode设置中文
  17. 11g等待事件之library cache: mutex X
  18. modbustcp封装使用获取设备数据示例
  19. oracle rowid 研究
  20. thinkcmf安装教程与目录结构详解 快速上手版