锐客网

  1. 首页 > it技术 > >

排序+|排序+ 前缀最值 寒假每日一题 奶牛过马路

题目：
每天，农夫约翰的 N 头奶牛都会穿过农场中间的马路。
考虑约翰的农场在二维平面的地图，马路沿水平方向延伸，马路的一侧由直线 y=0 描述，另一侧由直线 y=1 描述。
奶牛 ii 从马路一侧的位置 (ai,0)沿直线过马路到达另一侧的位置 (bi,1)。
所有 aiai 互不相同，所有 bibi 互不相同。
尽管他的奶牛们行动敏捷，他还是担心行动路径交叉的两头奶牛在过马路时发生碰撞。
约翰认为，如果一头奶牛的行动路径没有跟其他任何奶牛的行动路径相交，则该奶牛是安全的。
请帮助约翰计算安全奶牛的数量。
输入格式 第一行包含整数 N。
接下来 N 行，每行包含两个整数 ai,bi，用来描述一头牛的行动路径。
输出格式 输出安全奶牛的数量。
数据范围 1≤N≤10^5,
?10^6≤ai,bi≤10^6

【排序+|排序+ 前缀最值 寒假每日一题 奶牛过马路】
排序+|排序+ 前缀最值 寒假每日一题 奶牛过马路
文章图片
排序+|排序+ 前缀最值 寒假每日一题 奶牛过马路
文章图片




分析：我们怎么知道一头牛是否安全呢，我们将起始位置排序，我们只需要起始位置在它前面的牛的目标位置都在当前牛的目标位置前面，起始位置在它后面的牛的目标位置都在当前牛的目标位置后面，那么这头牛就一定是安全的，我们不必考虑如果有一组交叉线会同时使两头牛不“安全”，我们只需要考虑当前的这头牛安不安全即可。所以我们就是要求出前缀最大值和后缀最小值，分别与当前点进行比较，并且为了很好的使起始位置和目标位置串联起来，我们需要运用pair的结构。

代码：
#include
#define maxn 100010
#define x first
#define y second
using namespace std;
typedef pair PII;
PII a[maxn];
int S[maxn],T[maxn];
int main()
{
int n,cnt = 0;
cin >> n;
S[0] = -1000010; T[n+1] = 1000010;
for(int i = 1; i<=n; i++){
int m,b;
cin>>m>>b;
a[i].x = m ; a[i].y = b;
}
sort(a+1,a+n+1);
for(int i = 1; i<=n; i++) S[i] = max(S[i-1],a[i].y);
for(int i = n; i>0; i--) T[i] = min(T[i+1],a[i].y);
for(int i = 1; i<=n; i++){
if(a[i].y>=S[i-1] && a[i].y<=T[i+1]) cnt++;
}
cout< return 0;
}

    推荐阅读


    上一篇：操作数据库你不得不知道的|操作数据库你不得不知道的 事务 理念

    下一篇：ElasticSearch|ElasticSearch 文档（document）内部机制详解