当前位置:编程学习 > C/C++ >>

poj 2352

树状数组,模版题。。直接按给定的顺序统计比当前X小于等于的星星个数即可。

[cpp]
#include <cmath> 
#include <ctime> 
#include <iostream> 
#include <string> 
#include <vector> 
#include <cstdio> 
#include <cstdlib> 
#include <cstring> 
#include <queue> 
#include <map> 
#include <set> 
#include <algorithm> 
#include <cctype> 
#include <stack> 
#include <deque> 
using namespace std; 
typedef long long LL; 
#define EPS 10e-9 
#define INF 0x3f3f3f3f 
#define REP(i,n) for(int i=0; i<(n); i++) 
const int maxn = 40000; 
int c[maxn]; 
int ans[maxn]; 
int lowbit(int x)  { 
    return x&-x; 

void add(int x){ 
    while(x<maxn){ 
        c[x]+=1;   x+=lowbit(x); 
    } 
}  www.zzzyk.com
int sum(int x){ 
    int ret=0; 
    while(x>0){ 
       ret+=c[x];  x-=lowbit(x); 
    } 
    return ret; 

int main(){ 
    int n,x,y; 
    while(scanf("%d",&n)!=EOF){ 
        memset(ans,0,sizeof(ans)); 
        for(int i=0;i<n;i++){ 
             scanf("%d %d",&x,&y); 
             x++;y++; 
             ans[ sum(x)]++; 
 
             add(x); 
        } 
        for(int i=0;i<n;i++) 
        printf("%d\n",ans[i]); 
 
    } 
 
   return 0; 

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,