本文主要是介绍HDU - 1541 Stars,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题意:每颗星的左下角的星星的个数就是它的等级,求所有等级的星星个数
思路:因为已经按y坐标排序了,所以只要线段树x坐标就行了
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 32005;int tree[MAXN],level[MAXN];
int n;int lowbit(int x){return x&(-x);
}void update(int x,int d){while (x < MAXN){tree[x] += d;x += lowbit(x);}
}int sum(int x){int ans = 0;while (x > 0){ans += tree[x];x -= lowbit(x);}return ans;
}int main(){while (scanf("%d",&n) != EOF){memset(tree,0,sizeof(tree));memset(level,0,sizeof(level));for (int i = 1; i <= n; i++){int x,y;scanf("%d%d",&x,&y); level[sum(++x)]++;update(x,1);}for (int i = 0; i < n; i++)printf("%d\n",level[i]);} return 0;
}
这篇关于HDU - 1541 Stars的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!