hdu 3473 Minimum Sum

题目思路：划分数求中位数，需要新增一个sum数组，这样在查询的过程中就可以把小于中位数的数的总和求出来了。

[cpp] 
#include<stdio.h> 
#include<stdlib.h> 
#include<string.h> 
#include<string> 
#include<queue> 
#include<algorithm> 
#include<vector> 
#include<stack> 
#include<list> 
#include<iostream> 
#include<map> 
using namespace std; 
#define inf 0x3f3f3f3f 
#define M 110000 
int max(int a,int b) 
{ 
    return a>b?a:b; 
} 
int min(int a,int b) 
{ 
    return a<b?a:b; 
} 
__int64 ans; 
__int64 sum[20][M]; 
int s[20][M],tr[20][M]; 
struct node 
{ 
    int num,id; 
    bool operator<(const node a)const 
    { 
        return num<a.num; 
    } 
}sorted[M]; 
void build(int d,int l,int r) 
{ 
    if(l==r) 
    { 
          sum[d][l]=sum[d][l-1]+sorted[tr[d][l]].num; 
         return ; 
    } 
    int i,j,k,mid; 
    mid=(l+r)>>1; 
    j=l;k=mid+1; 
    for(i=l;i<=r;i++) 
    { 
        s[d][i]=s[d][i-1]; 
        sum[d][i]=sum[d][i-1]+sorted[tr[d][i]].num; 
        if(tr[d][i]<=mid) 
        { 
            s[d][i]++; 
            tr[d+1][j++]=tr[d][i]; 
        } 
        else 
            tr[d+1][k++]=tr[d][i]; 
    } 
    build(d+1,l,mid); 
    build(d+1,mid+1,r); 
} 
int query(int d,int lp,int rp,int l,int r,int k) 
{ 
 //   printf("lt %d rt %d ans %I64d\n",lp,rp,ans); 
    if(lp==rp) return tr[d][lp]; 
    int mid=(lp+rp)>>1; 
    if(s[d][r]-s[d][l-1]>=k) 
    { 
        ans+=(sum[d][r]-sum[d][l-1]); 
 
        int lt=lp+(s[d][l-1]-s[d][lp-1]); 
        int rt=lp+(s[d][r]-s[d][lp-1])-1; 
        ans-=sum[d+1][rt]-sum[d+1][lt-1]; 
        query(d+1,lp,mid,lt,rt,k); 
    } 
    else 
    { 
        ans-=sum[d][r]-sum[d][l-1]; 
      //  printf("lt %d rt %d ans %I64d\n",lp,rp,ans); 
        int lt=mid+1+(l-lp)-(s[d][l-1]-s[d][lp-1]); 
        int rt=mid+(r-lp+1)-(s[d][r]-s[d][lp-1]); 
        ans+=sum[d+1][rt]-sum[d+1][lt-1]; 
       // printf("lt %d rt %d ans %I64d\n",lt,rt,ans); 
        query(d+1,mid+1,rp,lt,rt,k-(s[d][r]-s[d][l-1])); 
    } 
} 
int main() 
{ 
    int t,i,n,m,count=1; 
    int l,r; 
    scanf("%d",&t); 
    while(t--) 
    { 
        scanf("%d",&n); 
        for(i=1;i<=n;i++) 
        { 
            scanf("%d",&tr[0][i]); 
            sorted[i].num=tr[0][i]; 
            sorted[i].id=i; 
        } 
        sort(sorted+1,sorted+n+1);// printf("akkk\n"); 
      //  int cnt=1; 
        for(i=1;i<=n;i++) 
        { 
            tr[0][sorted[i].id]=i; 
        } 
        for(i=0;i<20;i++) 
        { 
            s[i][0]=0; 
            sum[i][0]=0; 
        } 
        build(0,1,n); 
 
 
        scanf("%d",&m); 
      //  for(i=0;i<=2;i++) 
          //  for(int j=0;j<4;j++) 
            //    printf("i %d j %d sum %I64d \n",i,j,sum[i][j]); 
        printf("Case #%d:\n",count++); 
        while(m--) 
        { www.zzzyk.com
            scanf("%d%d",&l,&r); 
            ans=0; 
            l++;r++; 
            int tmp=query(0,1,n,l,r,(r-l+1)/2+1); 
          //  printf("k %d\n",(r-l+1)/2+1); 
            if((r-l+1)%2==0) 
                ans+=sorted[tmp].num; 
           // printf("tmp %d\n",tmp); 
            printf("%I64d\n",ans); 
        } 
        puts(""); 
    } 
} 

补充：软件开发 , C++ ,

上一个：算法导论十五章--矩阵链乘法
下一个：poj 3667 Hotel 线段树 内存分配问题