您的位置: 首页  >  IT文章  >  小石的妹子

小石的妹子

分类: IT文章 • 2023-10-28 22:12:42

题目链接

题目描述

小石有 n 个妹子，每个妹子都有一个细心程度 ai 和一个热心程度 bi，小石想给她们一个重要程度 ti（重要程度为 1 表示最重要，重要程度越小表示越重要）。
如果一个妹子 i 的细心程度和热心程度都比妹子 j 大，那么妹子 i 的重要程度要大于妹子 j 的重要程度，即妹子 i 比妹子 j 重要。
流程如下：
每次从所有没有重要程度的妹子中，找到若干妹子。对于这些妹子的任意一个，需要保证没有其他妹子比她更重要。然后把她们的重要程度标为 1 。下一次再从剩下没有重要程度的妹子中找到若干妹子，依然符合上述条件，然后把她们的重要程度标为 2，……，重复直到所有妹子都有自己的重要程度。
由于妹子太多，小石忙不过来，请你帮帮他。

输入描述:

第一行输入一个正整数 n，表示妹子的数量。
接下来 n 行，每行两个正整数
ai,bi，描述每个妹子的细心程度和热心程度。 保证所有的 ai 两两不等，所有的 bi 两两不等。

输出描述:

共 n 行，第 i 行输出一个正整数 ti 表示第 i 个妹子的重要程度。

示例1
5
1 4
2 2
3 3
4 1
5 5
输出
2
3
2
2
1
说明

第一轮取第 5 个妹子（5 5），因为没有其他妹子比她重要，标记为 1；

第二轮取编号为 1，3，4 的妹子，因为对于其中的任意一个妹子，都没有其他妹子比她们重要，标记为 2；

第三轮把编号为 2 的妹子标记为 3 。

备注:

(1≤n≤10 ^5,1≤ai,bi≤10^9)

ai，bi两两不等，所以不用考虑（5,5）,（4,5）,（4,4）这样数据，若是一个妹子重要程度为 num1,且a1>a2,则，要么b1<b2,要么b1>b2,
若是b1<b2,说明这两个妹子不能比较，但num1<=num2，只要找到ai>a2,bi>b2且numi最大的那个人，他的下一个人肯定就是（a2，b2)
若是b1>b2，则num1<=num2，但可能存在a1>ai>a2,b1>bi>b2,同样是找到ai>a2,bi>b2且numi最大的那个人再+1.
思路：先将a排序，要找一个人的ans时，在他前面的人的a都比他大，只要找到b比他大且ans最大的那个人+1就行了。先将b变成1到n，由于是动态查询，st不能用，只能用线段树。
代码：

#include<bits/stdc++.h>
using namespace std;
char buf[100000],*L=buf,*R=buf;
#define gc() L==R&&(R=(L=buf)+fread(buf,1,100000,stdin),L==R)?EOF:*L++
template<typename T>
inline void read(T&x) {
    int flag=x=0;
    char ch=gc();
    while (ch<'0'||ch>'9')flag|=ch=='-',ch=gc();
    while (ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch^48,ch=gc();
    if(flag)x=-x;
}
#define Init(arr,val) memset(arr,val,sizeof(arr))
const int inf=0x3f3f3f3f,mod=9999991,MAXN=1e5+8;
typedef long long ll;
int n;
struct Node {//妹子
    int a,b,pos;
}m[MAXN];
bool cmp1(const Node&x,const Node&y){return x.b<y.b;}
bool cmp2(const Node&x,const Node&y){return x.a>y.a;}
int ans[MAXN],tree[MAXN<<2];
void add(int i,int l,int r,int x,int val){//树上加点
    if(l==r){
        tree[i]=val;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid)add(i<<1,l,mid,x,val);
    else add(i<<1|1,mid+1,r,x,val);
    tree[i]=max(tree[i<<1],tree[i<<1|1]);
}
int query(int i,int l,int r,int x,int y){//在区间x，y查询
    if(x<=l&&r<=y)return tree[i];
    int mid=(l+r)>>1,res=-1;
    if(x<=mid)res=query(i<<1,l,mid,x,y);
    if(y>mid)res=max(res,query(i<<1|1,mid+1,r,x,y));
    return res;
}
int main() {
//    freopen("in.txt","r",stdin);
    read(n);
    for(int i=0; i<n; ++i) {
        read(m[i].a),read(m[i].b);
        m[i].pos=i;
    }
    sort(m,m+n,cmp1);
    for(int i=0;i<n;++i)m[i].b=i+1;
    sort(m,m+n,cmp2);
    for(int i=0;i<n;++i){
        ans[m[i].pos]=query(1,1,n+1,m[i].b+1,n+1)+1;
        add(1,1,n,m[i].b,ans[m[i].pos]);//加点。
    }
    for(int i=0;i<n;++i)printf("%d
",ans[i]);
    return 0;
}

相关推荐