题目描述
FST是一名可怜的小朋友,他很强,但是经常fst,所以rating一直低迷。
但是重点在于,他非常适合ACM!并在最近的区域赛中获得了不错的成绩。
拿到奖金后FST决定买一台新笔记本,但是FST发现,在价格能承受的范围内,笔记本的内存和速度是不可兼得的。
可是,有一些笔记本是被另外一些“完虐”的,也就是内存和速度都不高于另外某一个笔记本,现在FST想统计一下有多少笔记本被“完虐”。
但是重点在于,他非常适合ACM!并在最近的区域赛中获得了不错的成绩。
拿到奖金后FST决定买一台新笔记本,但是FST发现,在价格能承受的范围内,笔记本的内存和速度是不可兼得的。
可是,有一些笔记本是被另外一些“完虐”的,也就是内存和速度都不高于另外某一个笔记本,现在FST想统计一下有多少笔记本被“完虐”。
输入描述:
第一行一个正整数n, 表示笔记本的数量。接下来n行,每行两个正整数Mi,Si表示这款笔记本的内存和速度。 n≤105,Mi,Si≤109
输出描述:
一行,一个正整数,表示被完虐的笔记本数。
示例1
输入
4 100 700 200 500 50 100 300 400
输出
1
备注:
Mi和Si都是越大越优。 数据保证Mi互不相同,Si也互不相同。
思路
先对第一个关键字排序,然后根据第二个关键字进行遍历,因为已经按照第一个关键字从小到大排好了,只要前面有一个第二个关键字大于自己的,自己就算符合要求的,所有遍历的过程中更新最大值,再统计答案就行了。
代码
//Laptop(简单排序) #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int N = 1e5 + 10; struct S { int x; int y; bool operator < (const S t) const { if(this->x != t.x) return this->x > t.x; return this->y > t.y; } }; S s[N]; int main() { int n; scanf("%d" , &n); for(int i = 0 ; i < n ; i++) scanf("%d %d" , &s[i].x , &s[i].y); sort(s , s + n); int ans = 0 , mx = s[0].y; for(int i = 1 ; i < n ; i++) { if(s[i].y < mx) ans++; else mx = s[i].y; } printf("%d\n" , ans); return 0; }