树状数组求解为何WA5个点

P1168 中位数

星之海 @ 2018-01-11 13:23:46

#include<iostream>
#include<algorithm>
using namespace std;
int n,c[100001],a[100001];
int lowbit(int x)
{
    return x&-x;
}
void change(int x,int k)
{
    while(x<=n)
    {
        c[x]+=k;
        x+=lowbit(x);
    }
}
int sum(int x)
{
    int ans=0;
    while(x!=0)
    {
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}
int main()
{
    int i,k;
    cin>>n;
    for(i=1;i<=n;i++)
{
    cin>>a[i];
    //change(i,a[i]);
}
    sort(a+1,a+n+1);
    for(i=1;i<=n;i++)
    {
        change(i,a[i]);
        }
    k=(n+1)/2;
    for(i=1;i<=2*k-1;i+=2)
    {
        int x,y;
        x=i;
        y=sum(x)-sum(0);
        y/=i;
        cout<<y<<endl;
    }
    return 0;
}

|