Laptop(简单排序)
Laptop
https://ac.nowcoder.com/acm/problem/14266
题目描述
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;
} 牛客算法竞赛入门课第二节习题题解 文章被收录于专栏
入门课第二节习题题解
查看8道真题和解析