Wannfly模拟赛4 Laptop

题目链接:https://www.nowcoder.com/acm/contest/16/A

题意:略。

思路:先固定M,使其降序排列,然后对于当前的笔记本是否被完爆,只要看排在它前面的笔记本的最大的S值是否比它大即可确定,用前缀数组存一下前缀最大值就可以了。

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
struct Node{
    int x,y;
    bool operator<(const Node& rhs)const{
        return x>rhs.x;
    }
}po[maxn];
int n,m,pre[maxn];
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d%d",&po[i].x,&po[i].y);
    sort(po+1,po+1+n);
    pre[1]=po[1].y;
    for (int i=2;i<=n;i++) pre[i]=max(pre[i-1],po[i].y);
    int cnt=0;
    for (int i=2;i<=n;i++){
        if (pre[i-1]>=po[i].y) cnt++;
    }
    printf("%d\n",cnt);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注