`
Coco_young
  • 浏览: 125721 次
  • 性别: Icon_minigender_1
  • 来自: 湖南长沙
社区版块
存档分类
最新评论

[树状数组]HOJ 10069 星星的等级

 
阅读更多

传送门:http://acm.hnu.cn/online/?action=problem&type=show&id=10069&courseid=0

题目描述:给定若干个二维平面上 的点,如果a.x<=b.x&&a.y>=b.y则说a的等级比b高(如果a==b,则他们等级相同),要求对于每个点,输出比他等级高的点的总数。

解题思路:把星星按照y的递减序和x的递增序排序,然后对x轴建立树状数组,依次将每个星星插入树状数组(在插入前统计出1-当前坐标和区间和,记录下来),然后再把相同的星星的记录下来的数据换成他们之中第一个被插入树状数组的星星的值,即可,注意,需要离散化(即前面说的树状数组是在离散化后的x轴下建立起来的)

各种蛋疼:

1.如果比较函数不加最后的那句idx<s.idx那么就WA(应该这样写会导致排序的结果出现问题)

2.开始没看到(如果a==b,则他们等级相同)..

第一个问题比较蛋疼,以后需要注意!

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 111111;
struct Star{
    int x,y,idx;
    bool operator < (const Star &s) const{
        if(y!=s.y){
            return y>s.y;
        }else if(x!=s.x){
            return x<s.x;
        }else{
            return idx<s.idx;
        }//这。。。。。
    }
    bool operator == (const Star &s) const{
        return x==s.x&&y==s.y;
    }
}stars[MAXN];
int arr[MAXN],c[MAXN],res[MAXN],N,M;
int bs(int x){
    int l = 0, r = M-1,m;
    while(l<=r){
        m = (l+r)>>1;
        if(arr[m]==x)return m;
        else if(x<arr[m])r = m-1;
        else l = m+1;
    }
    return -1;
}
int lowbit(int x){
    return x&(-x);
}
int sum(int pos){
    int s = 0;
    while(pos>0){
        s+=c[pos];
        pos-=lowbit(pos);
    }
    return s;
}
void add(int pos){
    while(pos<=M){
        c[pos]++;
        pos+=lowbit(pos);
    }
}
int main(){
    while(scanf("%d",&N)!=EOF){
        memset(c,0,sizeof(c));
        M = 0;
        for(int i=0;i<N;i++){
            scanf("%d%d",&stars[i].x,&stars[i].y);
            stars[i].idx = i;
            arr[M++] = stars[i].x;
        }
        sort(arr,arr+M);
        int temp = 1;
        for(int i=1;i<M;i++)if(arr[i]!=arr[i-1])arr[temp++] = arr[i];
        M = temp;
        sort(stars,stars+N);
        for(int i=0;i<N;i++){
            int pos = bs(stars[i].x)+1;
            res[stars[i].idx] = sum(pos);
            add(pos);
        }
        for(int i=1;i<N;i++){
            if(stars[i]==stars[i-1])res[i]=res[i-1];
        }
        for(int i=0;i<N;i++){
            if(i) printf(" %d",res[i]);
            else printf("%d",res[i]);
        }
        printf("\n");
    }
    return 0;
}



分享到:
评论

相关推荐

    HOJ部分题目源代码

    2. **数据结构**:源代码可能会涉及链表、数组、栈、队列、树、图等基本数据结构的使用,以及高级数据结构如堆、哈希表、字典树等。 3. **数值计算与数学技巧**:中国余数定理的运用,以及其他数学方法如动态规划、...

    HOJ_1003_Java

    【标题】"HOJ_1003_Java"指的是在Hit Online Judge(简称HOJ)平台上的一道编程题目,其对应的解决方案是用Java语言编写的。这道题目可能涉及了算法、数据结构或者特定的编程概念,是检验和提升编程能力的一个实践...

    HOJ题目备份,值得拥有

    【标题】"HOJ题目备份,值得拥有"指的是在编程竞赛平台HOJ(华中科技大学在线评测系统)上的题目资源备份。这样的备份通常是为了防止数据丢失,方便参赛者或者编程爱好者随时查阅和练习过去的题目。 【描述】"HOJ...

    hoj小部分题

    【hoj小部分题】是针对HOJ(华中科技大学在线评测系统)中部分编程题目的集合,这些题目涵盖了不同的编程挑战,旨在帮助用户提升编程技能和算法理解。标签"hoj"表明这些题目来源于一个专门的编程竞赛或训练平台。...

    HOJ.rar_HOJ_hoj2055_oj_绘图软件

    【标题】"HOJ.rar_HOJ_hoj2055_oj_绘图软件" 涉及的主要是编程竞赛平台的相关知识,特别是针对杭州电子科技大学的ACM在线判题系统(Online Judge,简称OJ)的部分源代码。这个压缩包可能是用于教学或自我提升数据...

    hoj 离线题库 最新更新

    【标题】"hoj离线题库最新更新"所涉及的知识点主要集中在计算机科学与技术领域,特别是在线编程竞赛(Online Judge,简称OJ)的相关知识。hoj是众多在线编程竞赛平台之一,它提供了丰富的编程题目供用户进行训练和...

    hoj.rar_HOJ

    3. **理解数据结构**:深入理解数组、链表、树、图等数据结构的使用场景和实现方式。 4. **应对比赛**:为参加ACM/ICPC、CCPC等编程竞赛做准备。 5. **面试准备**:提升面试中的算法题解答能力,为求职加分。 总的...

    HOJ_1001_Java

    【标题】"HOJ_1001_Java"指的是在Hit Online Judge(简称HOJ)平台上的一道编程题目,该题目使用Java语言进行解答。HOJ是一个在线编程竞赛平台,它提供了各种算法题目供参赛者用不同编程语言解决,以此来提升编程...

    hoj.rar_hoj杭州

    标题中的"hoj.rar_hoj杭州"表明这是一个与杭州电子科技大学的在线判题系统(Online Judge,简称OJ)相关的压缩文件,其中包含了参赛者或学习者提交的代码。"hoj"通常指的是"杭电OJ",一个用于编程竞赛和训练的平台。...

    HOj DP 分类 Zhouguyue

    ### 知识点概述 根据提供的文件信息,可以推断出该列表主要涉及了一系列与**动态规划(Dynamic Programming,简称DP)**相关的编程题目。这些题目来自不同的问题集,覆盖了多个方面,如序列处理、游戏策略、路径...

    HOJ简单题400道源码

    acm简单题集,适合初学者交流,400道简单题

    HOJ1002:A+B+C

    注意数据范围,所以要用long long

    哈工大hoj1037

    哈工大hoj1037,详细的源代码,附有注释,可以看懂。

    c在线题库(hoj)

    c在线题库,希望大家下载 kjbjbk lnknn 你看了可能地方辅导书幅度不断说

    hoj-judger:HydrogenOJ的简单沙箱和判断器

    GRUB_CMDLINE_LINUX="cgroup_enable=memory swapaccount=1"然后运行以下命令: update-grub && reboot在Node.js项目中安装要求:纱线yarn add hoj-judger自己建造要求:CMake 3.4或更高版本,g ++ 9或更高版本./...

    hit.rar_HIT-acm-HOJ-answer_算法 课件_课件

    【标题】"hit.rar HIT-acm-HOJ-answer_算法 课件_课件" 提供的资源主要围绕着算法分析这一主题,其中包含了课件和习题,旨在帮助学习者深入理解和掌握算法设计与分析的技巧。HIT可能指的是哈尔滨工业大学(Harbin ...

    HOJ matrix 源代码

    采用暴力的思想,搜索所有可能路径。 int matrix[7][7]; int n; void inttoseries(int i,int *s) //将数i化为n进制的n位数 {int k,j; for(k=0,j=i;k;++k) {s[k]=j%n;j/=n;} } int maxcolumn(int *s)//每列最大和 ...

    hoj-master.zip

    基于SpringCloud与Vue前后端分离,分布式架构的在线测评平台OJ (An open source online judge system base on SpringBoot, Springcloud Alibaba and Vue.js !)

    hoj2196 01背包.cpp

    01背包问题 #include #include #include #include #include using namespace std; int f[2700]; int w[600]; int val[600]; int main() { freopen("in","r",stdin); int t,tt,n,a,b; ... {

    Hcode Online Judge(HOJ):基于SpringCloud与Vue前后端分离,分布式架构的在线测评平台.zip

    Hcode Online Judge(HOJ):基于SpringCloud与Vue前后端分离,分布式架构的在线测评平台.zip

Global site tag (gtag.js) - Google Analytics