方法更好的解决方案 - 中位数之和 [英] Approach for better solution - Sum of medians

问题描述

以下是 Spoj-WEIRDFN 的问题

问题：

让我们定义：

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] 。

where M[i] is the median of the array {F[1],F[2],..,F[i-1]} Given a,b,c and n, calculate the sum 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;
}

任何人都可以提供更好的算法或数据结构提示这个任务

推荐答案

对于每个测试用例，您可以维护二叉搜索树，因此您可以在 O（log n）时间，而您只需要O（log n）时间在树中添加一个新元素。

For each test case, you can maintain a binary search tree, thus you can find the median of n elements in O(log n) time, and you only need O(log n) time to add a new element into the tree.

因此，我们有一个 O（T * nlogn）算法，T是测试用例数，n是元素的数量，这应该足够通过。

Thus, we have an O(T*nlogn) algorithm, with T is number of test case, and n is number of elements, which should be enough to pass.

这篇关于方法更好的解决方案 - 中位数之和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！