更好解决方案的方法 - 中位数之和

Question

问题:

让我们定义：

F[1] = 1
F[i] = (a*M[i] + b*i + c)%1000000007 for i > 1

其中 M[i] 是数组的中位数 {F[1],F[2],..,F[i-1]} 给定 a,b,c 和 n，计算总和 F[1] + F[2] + .. + F[n].

约束:

0 <= a,b,c < 1000000007
1 <= n <= 200000

我想出了一个不太有效的解决方案

我的解决方案::--

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define mod 1000000007
int main() {
    // your code goes here
    int t;
    scanf("%d",&t);
    while(t--)
    {
      ll a,b,c,sum=0;
      int n;
      scanf("%lld%lld%lld%d",&a,&b,&c,&n);
      ll f[n+1];
      f[1]=1;
      f[0]=0;
      for(int i=2;i<=n;i++)
      {  
          ll temp;
          sort(&f[1],&f[i]);
          temp=f[i/2];
          f[i]=((a*(temp)%mod)+((b*i)%mod)+(c%mod))%mod;
          sum+=f[i];
      }
      printf("%lld\n",sum+f[1]);
    }
    return 0;
}

任何人都可以给我提示以获得更好的算法或数据结构来完成这项任务

Answer 1

对于每个测试用例，你可以维护一个binary search tree, thus you can find the median of n elements in O(log n) time，你只需要O(log n)时间来向树中添加一个新元素。

因此，我们有一个 O(T*nlogn) 算法，其中 T 是测试用例的数量，n 是元素的数量，应该足以通过。

更好解决方案的方法 - 中位数之和

Approach for better solution - Sum of medians

algorithm

data-structures