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

poj 2299

树状数组 +离散化。
我一开始用的 map+树状数组暴搞。。哪知超时了。  这题如果用树状数组,还是需要离散化才行。。
离散化的步骤就是, 先用一个结构体,用num 保存 原来的数,id保存原来数组所在的位置。。然后按num排序,那么得到一个从小到大有序的序列。 然后通过id找到原数组所在的位置,并用另一个数组存放 通过映射得到的新的类似原来(比原来数组的值缩小了,但是相对应的大小关系不变)序列的数组。
[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 = 500500; 
int a[maxn],c[maxn],aa[maxn]; 
struct node{ 
    int num,id; 
    bool operator <(const node & b) const { 
        return num<b.num; 
    } 
}b[maxn]; 
int lowbit(int x){ 
    return x&-x; 

int add(int x){ 
    while(x<maxn){ 
        c[x]+=1;   x+=lowbit(x); 
    } 

LL sum(int x){ 
    LL ret=0; 
    while(x>0){ 
       ret+=c[x];  x-=lowbit(x); 
    } 
    return ret; 

int main(){ 
    int n; 
    while(scanf("%d",&n)!=EOF){ 
        memset(c,0,sizeof(c)); 
        if(n==0) break; 
        for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i].num=a[i],b[i].id=i; 
        sort(b+1,b+1+n); 
        aa[ b[1].id ]=1; 
        for(int i=2;i<=n;i++){ 
            if(b[i].num==b[i-1].num){ 
                 aa[ b[i].id ]=aa[ b[i-1].id ]; 
            } 
            else aa[ b[i].id ]=i; 
        } 
        LL ans=0; 
        for(int i=n;i>=1;i--){ 
           ans+=sum(aa[i]-1); 
           add(aa[i]); 
        } 
        printf("%lld\n",ans); 
    } 
   return 0; 

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