南昌网站建设风格,短网址生成源码,淘宝客网站建好了没有数据库,佛山网站设计中心正题
题目链接: http://poj.org/problem?id2352 题意
有n个坐标不同的星星#xff0c;一个星星的等级等于在它左下的所有星星数量#xff0c;求各个等级的星星数。 注#xff1a;输入顺序保证Y坐标是升序#xff0c;Y坐标相同的情况下X坐标也是升序的。 解题思路
用树…正题
题目链接: http://poj.org/problem?id2352 题意
有n个坐标不同的星星一个星星的等级等于在它左下的所有星星数量求各个等级的星星数。 注输入顺序保证Y坐标是升序Y坐标相同的情况下X坐标也是升序的。 解题思路
用树状数组表示在x坐标上有多少个星星因为Y坐标升序输入所以不用考虑Y坐标然后用树状数组求1到x坐标上的星星总数就好了。 代码
#includecstdio
#includealgorithm
using namespace std;
int c[82010],w[15001],n,s,pre,a;
int lowbit(int x)
{return x(x^(x-1));}
void change(int x,int num)//修改
{int ix;while(i82000){c[i]num;ilowbit(i);}
}
int getsum(int x)//求值
{int sum0;while (x0){sumc[x];x-lowbit(x);}return sum;
}
int main()
{scanf(%d,n);for (int i1;in;i){scanf(%d%d,a,w[i]);a;//避免读入0死循环w[i]getsum(a);//就等级change(a,1);//插入该星星}sort(w1,w1n);//排序prew[1];s1;for (int i2;in;i){if (w[i]!pre)//等级不相同{printf(%d\n,s);for (int jpre1;jw[i];j) //输出中间printf(0\n);prew[i];s1;}else s;}printf(%d\n,s);for (int ipre1;in;i) printf(0\n);//输出剩余的
}
