题面

题意

  给出序列 \(\{a_n\}\) 和 \(k\;(0.01 < k \le 0.35)\)，求 \(s_i=\sum_{j=1}^{\lfloor k \cdot a_i \rfloor} \frac{a_i \cdot a_j}{i-j}\)。允许相对误差 \(\le 0.05\)。

题解

  理论上，这道题无法在规定时间内求出精确解，但由于允许相对误差较大，可以考虑在损失一定精度的情况下求出近似解。

  因为 \(j\) 在 \(\pm 0.02\cdot i\) 的范围内浮动时对答案的影响不会超过限制，所以一个思路是将一定范围内的相邻行星合并成一个。因为对于不同的 \(i\)，可以接受的范围也不同，因此考虑直接限制最多同时存在的行星数量，维护每个行星（集）的重量，位置和内含行星数（用于合并时加权计算出合并后的位置）。当行星数量超过阈值时，将相邻行星两两合并以限制总数。

代码

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
typedef long double ld;
typedef long long ll;
const double ee=1e-9;
const int maxn=1e5,lim=50;
struct node{
    ld wei,pos;
    int cnt;
    node(ld wei=0,ld pos=0,int cnt=1):wei(wei),pos(pos),cnt(cnt){}
};
node operator + (const node &a,const node &b){
    node nd;
    nd.wei=a.wei+b.wei;
    nd.pos=(a.pos*a.cnt+b.pos*b.cnt)/(a.cnt+b.cnt);
    nd.cnt=a.cnt+b.cnt;
    return nd;
}
int a[maxn];
node que[maxn];
int siz,rep;
void add(const node &nd){
    if (siz&&que[siz-1].cnt<rep)
        que[siz-1]=que[siz-1]+nd;
    else que[siz++]=nd;
    if (siz<lim*2) return;
    int i;
    for (i=0;i<lim;i++)
        que[i]=que[i*2]+que[i*2+1];
    siz=lim; rep*=2;
}
double get(ld wei,ld pos){
    int i;
    double ans=0;
    for (i=0;i<siz;i++)
        ans+=wei*que[i].wei/(pos-que[i].pos);
    return (double)ans;
}
int main(){
    int i,n,m;
    double k;
    scanf("%d%lf",&n,&k);
    m=1; rep=1;
    for (i=1;i<=n;i++){
        scanf("%d",&a[i]);
        while (m<=i*k+ee){
            add(node(a[m],m,1)); m++;
        }
        printf("%.12f\n",get(a[i],i));
    }
    return 0;
}