Laptop

题目描述

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

输入描述:

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

输出描述:

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

输入

4
100 700
200 500
50 100
300 400

输出

1

题目大意

n个笔记本，如果笔记本的内存和速度都小于等于另外一个笔记本，则被完虐，求多少笔记本被完虐

思路

排序+max，注意不要理解成一个笔记本要小于所有笔记本
1.先排序a
2.再求出i后b的最大值c
3.如果i的b<i+1的c则被完虐

#include<bits/stdc++.h>
using namespace std;
struct date{
    int a=0;
    int b=0;
    int c=0;
}num[100005];
bool cmp(date a,date b){
    if(a.a==b.a)
    {
        return a.b<b.b;
    }else
    return a.a<b.a;
}
int main()
{
    int n,sum=0,maxn=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d%d",&num[i].a,&num[i].b);
    }
    sort(num,num+n,cmp);
    for(int i=n-1;i>=0;i--)
    {
        maxn=max(maxn,num[i].b);
        num[i].c=maxn;
    }
    for(int i=0;i<n;i++)
    {
        //printf("%d %d %d\n",num[i].a,num[i].b,num[i].c); 
        if(num[i].b<=num[i+1].c)
        {
            sum++;
        }
    }
    printf("%d",sum);
    return 0;
}