时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 131072K,其他语言262144K
一、题目内容
题目描述
FST是一名可怜的小朋友,他很强,但是经常fst,所以rating一直低迷。
但是重点在于,他非常适合ACM!并在最近的区域赛中获得了不错的成绩。
拿到奖金后FST决定买一台新笔记本,但是FST发现,在价格能承受的范围内,笔记本的内存和速度是不可兼得的。
可是,有一些笔记本是被另外一些“完虐”的,也就是内存和速度都不高于另外某一个笔记本,现在FST想统计一下有多少笔记本被“完虐”。
输入描述
第一行一个正整数n,
表示笔记本的数量。接下来n行,每行两个正整数Mi,Si表示这款笔记本的内存和速度。
n≤10^5,Mi,Si ≤10^9。
输出描述
一行,一个正整数,表示被完虐的笔记本数。
示例1
输入
4
100 700
200 500
50 100
300 400输出
1
备注
数据保证Mi互不相同,Si也互不相同
二、解题思路
依据题意,只要被其中一个笔记本完虐即+1,这里,我们可以直接暴力枚举,遇到完虐将结果+1,break退出内循环,直至所有都比较一次,输出结果即可。当然,这中间过程我们可以进行优化,比如在比较之前先将笔记本性能有低到高排序(内存为主、速度为次,多条件排序),然后再进行比较,这里可以进行逆序比较,原因是Mi,Si越大,性能越优越,越容易完虐其他机器。
代码实操
#include<bits/stdc++.h>
using namespace std;
struct Node {
int m,s;
bool friend operator < (Node a, Node b){
return a.m == b.m ? (a.m < b.m) : (a.s < b.s);
}
}p[100010];
int main() {
int n;
cin >> n;
for(int i = 0; i < n; i++) {
cin >> p[i].m >> p[i].s;
}
sort(p, p + n);
int result = 0;
for(int i = 0; i < n - 1; i++) {
int m = p[i].m;
int s = p[i].s;
for(int j = n - 1; j > i; j--) {
if (s < p[j].s && m < p[j].m) {
result++;
break;
}
s = p[i].s;
m = p[i].m;
}
}
cout << result << endl;
return 0;
}