题目

题目描述：
FST是一名可怜的小朋友，他很强，但是经常fst，所以rating一直低迷。
但是重点在于，他非常适合ACM！并在最近的区域赛中获得了不错的成绩。
拿到奖金后FST决定买一台新笔记本，但是FST发现，在价格能承受的范围内，笔记本的内存和速度是不可兼得的。
可是，有一些笔记本是被另外一些“完虐”的，也就是内存和速度都不高于另外某一个笔记本，现在FST想统计一下有多少笔记本被“完虐”。

输入描述：
第一行一个正整数n。
表示笔记本的数量。接下来n行，每行两个正整数Mi，Si表示这款笔记本的内存和速度。
n≤105,Mi,Si≤109

输出描述：
一行，一个正整数，表示被完虐的笔记本数。

解析

知识点

  • 这道题主要的考点就是：简单排序，但是这题数据比较弱，暴力都可以暴力出来。

暴力求解

  1. 这道题暴力起来完全不难：就是去判断每一个点是不是一个fw的点。
  2. 所以对于每个点去遍历一下所有的点就好了。判断了自己是fw就退出来。
  3. 嗯，就没了。

排序求解

  1. 排序求解有什么好的？就是一个优雅一点的暴力而已咯。
  2. 我们排序就按照其中一个排序就行了（我们假设两个因素称为A和B）。
  3. A排好序之后呢，我们这个序列就有了一个特点，就是后面的所有物品的A值都比前面的废物。
  4. 所有相当于我们现在只要知道某一个物品的B值，ta比排序在ta前面的物品的B值fw，他就是fw（为什么要是前面的呢？因为只有前面的A值是不fw的呀）。
  5. 嗯，就这样。

算法操作

  • 那怎么操作？这个简单，只要用一个变量经存下来已比遍历过的最大B值，和当前B值比较一下就好了。

看我代码

  1. 输入。
  2. 排序。
  3. 遍历。
  4. 输出。

AC代码（暴力枚举） 

#include <iostream>
#include <utility>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

const int MAX = 1e5 + 7;
pair<int, int> info[MAX];
//全局变量区

int main() {
    IOS;
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> info[i].first >> info[i].second;
    //输入数据
    int cnt = 0;
    for (int i = 1; i <= n; i++) { //循环遍历每个节点，判断他是不是fw
        int M = info[i].first, S = info[i].second;
        for (int j = 1; j <= n; j++)//循环遍历其他点，证明他是不是fw
            if (i != j && M <= info[j].first && S <= info[j].second)  {
                cnt++;
                break;
            }        
    }
    //统计被完虐的数量
    cout << cnt << endl;
    //输出
    return 0;
}
//函数区

AC代码（简单排序） 

#include <iostream>
#include <algorithm>
#include <utility>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

const int MAX = 1e5 + 7;
pair<int, int> info[MAX];
//全局变量区

bool cmp(const pair<int, int>& u, const pair<int, int>& v) {
    if (u.first == v.first) return u.second > v.second;
    return u.first > v.first;
}
//函数预定义区

int main() {
    IOS;
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> info[i].first >> info[i].second;
    //输入数据
    sort(info + 1, info + 1 + n, cmp);
    //排序
    int cnt = 0, mx = info[1].second;
    for (int i = 2; i <= n; i++) {
        if (mx < info[i].second) mx = info[i].second;
        else cnt++;
    }
    //统计被完虐的数量
    cout << cnt << endl;
    //输出
    return 0;
}
//函数区