首页 > 代码库 > POJ 2352 （stars）

POJ 2352 （stars）

2024-07-16 10:31:55   227人阅读

【题意描述】

就是给定n个星星的x,y坐标，y坐标按照从小到大的顺序进行排列，x坐标随机排列。下面求对于每个星星而言，其它星星的x,y的坐标都小于等于该星星的数目，然后输出所有的情况。

【思路分析】

我们这道题可以采用树状数组求解，将x+1作为树状数组的底标。

【AC代码】

#include<iostream>  #include<bitset>  #include<cstdio>  #include<cstring>  #include<algorithm>  #include<string>  #include<cstdlib>    using namespace std;    #define MAXN 40000      int n;  int c[MAXN];  //树状数组   int a[MAXN];int x_c[MAXN];  int lowbit(int t)  {      return t&(-t);  }  int sum(int i)  {      int s=0;      while(i>0)      {          s+=c[i];          i-=lowbit(i);      }      return s;  }    void modify(int i,int x)  {      while(i<=MAXN)      {          c[i]+=x;          i+=lowbit(i);         }   }    void solve()  {         int x;      memset(a,0,sizeof(a));      memset(c,0,sizeof(c));      for(int i=1;i<=n;i++)      {          scanf("%d",&x);          a[sum(x+1)]++;//由于是采用lowbit技术时值一定要大于0，对于x=0的情况，所以把所有的x+1.        modify(x+1,1);          scanf("%d",&x);      }     for(int k=0;k<n;k++)      {          printf("%d\n",a[k]);      }            }    int main()  {      while(scanf("%d",&n)!=EOF)          solve();      return 0;  }

 


联系
我们