由积分排名想到的一道算法题目《欢迎大家求解》

由积分排行想到的一道算法题目《欢迎大家求解》
比如****的积分形式（以下为假设），每当你获得一次积分，服务器便保留这时的时间以及总分。现在要求在哪一段时间内获得积分的效率最高（前提这段时间内最少获得100分）。求一个时间复杂度低于n^2的算法。除了穷举的算法O（n^2)，有没有时间复杂度更低的算法呢？

以二维数组模拟以上问题（以下为一个例子）

时间总分
0 0
10 5
30 28
44 71
99 97
110 105
125 120
198 181
203 190
230 201

时间和总分都是严格递增的。
效率计算方法举例：比如在时间段30到110之间的效率为（105-28）/（110-30）。

------解决方案--------------------
主要是要做得好有难度...办法肯定是有的...
------解决方案--------------------
我有两个问题：
1. 时间间隔不等长，能否让间隔等长？这样可以简化一下问题处理，且并没有失去你原有的意图。
2. “前提这段时间内最少获得100分”这句话不是很明白，是两个领进时刻之间所获得的分数必须超过100吗？如果是这样的话，楼主给出的那个示例数据中，是不是没有一个符合这个条件的？

请解释。
------解决方案--------------------
领进 = 临近

------解决方案--------------------

C/C++ code


#include <stdio.h>
#include <math.h>
#include <iostream>
using namespace std;
/*
0 0
10 5
30 28
44 71
99 97
110 105
125 120
198 181
203 190
230 201
*/

double Time[]={0,10,30,44,99,110,125,198,203,230};
double score[]={0,5,28,71,97,105,120,181,190,201};
double Time1[20]={0};
double score1[20]={0};
double t=0,s=0;
double begin =0,end=0;
double MaxSum()
{
  for(int i=1; i <10;i++)
  {
    Time1[i] = Time[i]-Time[i-1]; //把后一个减前一个的结果都保存下来
    score1[i] = score[i] - score[i-1];        
  }    
  //最大子段和 
  double res =0;
  for(int i=1;i<10;i++)
  {
    if((s+score1[i])/(t+Time1[i]) < score1[i]/Time1[i]) 
    {
      t = Time1[i]; 
      s = score1[i];    
    } 
    else
    {
      t +=     Time1[i];
      s +=  score1[i];
    }
    if(s/t > res) res = s/t;
  }
  return res;
}

double fun()
{
    //O(n*n)算法求得结果  
  double res =0;
  for(int i=1;i<10;i++)
  for(int j=0;j<i;j++)
  {
    double tmp =(score[i]-score[j])/(Time[i]-Time[j]);
    if(tmp > res)
    {
      res = tmp;
      begin = j;
      end = i;
    }         
  }    
    return res;
}
int main()
{
  double res = MaxSum();
  cout<<"time="<<t<<" score="<<s<<endl;
  cout<<res<<endl;
  
  res = fun();
  cout<<"begin="<<begin<<" end="<<end<<endl;
   cout<<res<<endl;
  system("pause");
  return 0;
}

------解决方案--------------------
有n*log(n)的方法，如果给出的数据有序，还可以优化到O(n)，方法就是斜率优化，维护一个凸包，只考虑凸包上的点，本身还是O(n)个状态，但使用单调队列可以让状态转移变成O(1)的，具体实现比较复杂，lz查查相关资料吧。

------解决方案--------------------
在时间-积分曲线上求导数,导数最大的地方积分最快
效率正比于得分次数n,或者正比于时间(看算法)

------解决方案--------------------
楼主，这是一维DP啊，我想起了以前ACM的时光。。。我只能想到NLOGN的……

------解决方案--------------------
用两个指针，一个在前一个在后，初始化这一段积分最少为100分，算出平均斜率。
1.后指针往后移，当且仅当后一段的斜率大于平均斜率，如果条件不满足，后指针停止前进。（跳到下一位）
2.前指针往后移，当且仅当后一段斜率大于平均斜率并且这一段积分最少为100分，不满足条件则停止。（跳到下一位）
3.重复1，2，如果后指针到最后一位，则停止前进。转为执行2.
4.两指针都不能动了，那么最高的效率段就出来了

------解决方案--------------------
注意，我所说的平均斜率是两个指针之间那一段的平均斜率

------解决方案--------------------

探讨

用两个指针，一个在前一个在后，初始化这一段积分最少为100分，算出平均斜率。
1.后指针往后移，当且仅当后一段的斜率大于平均斜率，如果条件不满足，后指针停止前进。（跳到下一位）
2.前指针往后移，当且仅当后一段斜率大于平均斜率并且这一段积分最少为100分，不满足条件则停止。（跳到下一位）
3.重复1，2，如果后指针到最后一位，则停止前进。转为执行2.
4.两指针都不能动了，那么最高的效率……

------解决方案--------------------
看了算法，我觉得我的智商可以忽略为零了。
------解决方案--------------------

由积分排名想到的一道算法题目《欢迎大家求解》

相关推荐