思维

链接：https://ac.nowcoder.com/acm/problem/14266
来源：牛客网

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

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

输出描述:

一行，一个正整数，表示被完虐的笔记本数。

示例1
输入
复制

4
100 700
200 500
50 100
300 400

输出
复制

1

解析：首先判断数据量10e5，所以不能用常用的 的算法。题意是找出能被完爆的笔记本，我们可以对整个数据进行排序,由其中一个元素，大到小遍历，同时维护一个最大值，用来去和后面的内容比较。因为后面数的前提是，有一个元素比前面的小，所以后面的数据x的比较方式就直接和x之前的最大值的元素比较，保证能被完爆，时间复杂度 。

code

#include<bits/stdc++.h>
using namespace  std;
typedef long long ll;
const ll N = 100000;
const ll Mod = 1000000009;
stack <char> st;
struct  asd
{
    int m;
    int s;
}a[N+5];
int ans = 0;
bool cmp(asd q, asd p)
{
    return q.m>  p.m;

}
int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int m, s;
        cin >> m >> s;
        a[i].m = m;
        a[i].s = s;
    }
    sort(a, a + n, cmp);

    int maxl = a[0].s;
    for (int i = 1; i < n; i++)
    {
        if (a[i].s > maxl)//
        {
            maxl = a[i].s;
        }
        else
        {
            ans++;
        }
    }
    cout << ans << endl;
}