蓝桥杯真题——数星星
输入样例:
5
1 1
5 1
7 1
3 3
5 5
输出样例:
1
2
1
1
0
分析:
根据题目,是逐行读入数据,我们要求每颗星星左下方的星星数量,就是要迅速求一个区间内的值
于是我们联想到树状数组来解决问题
代码演示:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;const int N = 15010,M = N*2;
int n;
int tr[M],level[N];// 树状数组的基本三个函数
int lowbit(int x)
{return x&-x;
}// 寻找前驱结点,快速得到前缀和
int query(int x)
{int res = 0;for(int i=x;i;i-=lowbit(i)){res+=tr[i];}return res;
}// 改变某一个数的值,要将祖先也改变
void add(int x,int v)
{for(int i=x;i<M;i+=lowbit(i))tr[i]+=v;return;
}int main(void)
{scanf("%d",&n);for(int i=0;i<n;i++){int x,y;scanf("%d%d",&x,&y);// lowbit(0)=0会导致死循环// 要将所有坐标向右平移一个点位,不影响 x++;// 看前面有没有存储的值 int t = query(x);// 星星值 level[t]++;// 构造树状数组 add(x,1);}for(int i=0;i<n;i++){scanf("%d\n",level[i]);}return 0;
}
感谢查看!