由积分排行想到的一道算法题目《欢迎大家求解》
比如CSDN的积分形式（以下为假设），每当你获得一次积分，服务器便保留这时的时间以及总分。现在要求在哪一段时间内获得积分的效率最高（前提这段时间内最少获得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 010 530 2844 7199 97110 105125 120198 181203 190230 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.两指针都不能动了，那么最高的效率段就出来了
[解决办法]
注意，我所说的平均斜率是两个指针之间那一段的平均斜率
[解决办法]
[解决办法]
看了算法，我觉得我的智商可以忽略为零了。
------解决方案--------------------
好吧， 我给出一个原始算法的优化版吧：
原始算法：两层循环，一个扫头一个扫尾，记录最优解的斜率。复杂度是 O(N^2)。
优化算法:
显然，有一点事实可以利用起来， 最优解无法被拆分成两个分数 >= 100的子段。 因为假如最优解可以拆分成两个分数 >= 100的子段，那么显然，这两个子段都是合法的，并且至少一个子段的斜率 >= 原始段的斜率。 这将意味着第二层循环不需要扫描全部的数组。
设一个数组Next[i]，记录下一个比节点i高出至少100分的节点位置。
显然，第一个层循环遍历头节点，第二层循环遍历尾节点就只需要遍历 区间 Next[i] -> Next[Next[i]] 之间的节点就可以了。 由于每个节点至少涨一分，因此 Next[i] -> Next[Next[i]] 在最坏的情况下只有100个点。
因此算法复杂度在最坏的情况下是： O(100 * N)。
虽说是个线性算法，但前面的系数比较大，只有N很大的情况下才能体现出优势，倘若 N < 100 ，就没啥意义。
另外关于 Next[i] 数组的求法，这个可以在O(N)的复杂度求出：
memset(Next, 0x7F, sizeof Next); // 初始化为无穷大，表示没有满足条件的位置存在
for (i = 0, j = 1; i < N && j < N; )
{
if (Score[j] - Score[i] >= 100)
{
Next[i] = j;
++i;
}
else
{
++j;
}
}
[解决办法]
另外，看了下楼主的代码。 有个建议，像这种斜率大小的比较，不建议用浮点数来做除法，因为浮点除法存在精度问题，这种精度问题可能随着运算的反复进行而逐渐放大并影响最终结果。
比较 A/B 与 C/D 大小应该用交叉相乘转化为 比较 A * D 和 B * C的大小， 这样可以避免浮点带来的精度问题。 因此存储斜率应该用两个元素来存储，一个分子，一个分母，比较时则用交叉相乘法比较。
[解决办法]
lz看看这篇文章中的例2吧，讲的比较清楚，凸包部分明白之后，剩下的都好理解。编程稍微复杂一点的地方在于，不能先处理完整个的凸包再找，而是需要一边建立凸包一边找。
http://wenku.baidu.com/view/b97cd22d0066f5335a8121a3.html
[解决办法]
[解决办法]
哦，好像我这种算法也没把所有的情况考虑进去
[解决办法]
[解决办法]
这里有一点点理解上的问题：
积分是以时间点为单位获得的。
比如，如果input为：
0 0
5 10
10 20
20 100
实际上的获得积分的情况为：
0 0
5 10
10 10
20 80 （在这一点获得了80分）
定义 slope = 在单位时间内获得的最大积分，那么明显在 10~20区间内，slope最大，为：100/(20-10) = 10。
但题目给的理解方式为，积分差 = A时间点得分 - B时间点得分，这实际上是从一个得了分的时间点之后开始算的，但没有算这个时间点的得分（就是说，多算了A时间点之后到A之后第一次得分之前的时间）。
明显这样的计算方式并不能算出最大的slope。
[解决办法]
（居然不能编辑自己发过的帖子……CSDN真的是不人性化）
不好意思啊……刚刚有一点输入错误，忽略上一个帖子吧，看这个：
积分是以时间点为单位获得的。
比如，如果input为：
0 0
5 10
10 20
20 100
实际上的获得积分的情况为：
0 0
5 10
10 10
20 80 （在这一点获得了80分）
定义 slope = 在单位时间内获得的最大积分，那么明显在 5~20区间内，slope最大，为：100/(20-5) = 6.67。
但题目给的理解方式为，积分差 = A时间点得分 - B时间点得分；所以依照这个方法计算，slope = 100/（20-0）= 5；这实际上是从一个得了分的时间点之后开始算的，但没有算这个时间点的得分（就是说，多算了A时间点之后到A之后第一次得分之前的时间）。
明显这样的计算方式并不能算出最大的slope。
[解决办法]
[解决办法]
[解决办法]
想出一个O（nlogn）的算法。
用构建赫夫曼树的方法可实现，只需其中的优先队列换成同样时间复杂度的红黑树。
计算过程：
分别计算出所有相邻两个时刻间的得分效率。加入红黑树。
每次从红黑树中选出效率最高的点A，前一时段的点B和后一时段的点C，A与B和C分别和并，得到两个点加入红黑树，直到找到分数大于100的点。算法结束
稍后我写个C++程序贴上来。
[解决办法]
[解决办法]
OK，我来说明下楼上code的思路（其实个人感觉，代码里面的注释我给的还是很充分的，应该
能看懂）：
这个方法的time complexity: O(n) ~~~
为了思考方便，首先我做了一个坐标系的转化：
把time看成纵坐标（y轴），score看成横坐标（x轴）；这样问题转化为，求在Δscore （即Δx
）>= 100 （为了一般性，我在代码里面用scoreInterval表示这个数字）的时候，使得slope最
小的 startIndex 和 endIndex。
假设一共输入了n组数据。（代码中的 score.size()等价于n）
*****************************preprocess***************************************
建立两个表：predecessor[n]， minSlopeStartIndexTable[n];
第一个表，predecessor[i]表示：
对于index i，startIndex = predecessor[i]是i之前的第一个使得 Δscore = score
[i] - score[startIndex] >= scoreInterval 的 startIndex。对应的建表方法见code。这步
需要 O(n)的时间。
第二个表，minSlopeStartIndexTable[n]表示：
对于index i，假设 sIndex = minSlopeStartIndexTable[i]，那么 对于j = 从index
0开始，到index i，使得 所有终结于i的点中，slope(j,i)的值为最小的，记为sIndex，存储
在这个表中。
易知递归关系有：
minSlopeStartIndexTable[i] =
(slope(minSlopeStartIndexTable[i-1],i)<slope(i-1,i))?
minSlopeStartIndexTable[i-1]:i-1;
这一步需要O(n)的时间。
*****************************calculation***************************************
于是我们开始进行计算：
保持一个minSlope：这是进行到当前计算状态中，能得到的最小的slope。初始化为正无穷
（INF，一个非常大的数值）
同时有bestStartIndex，bestEndIndex表示对应minSlope的两个index。
对于index i：
假设：minSlope是从0~i-1中所有可能中的最小斜率。
首先我们需要计算从predecessor[i]到i的斜率，同minSlope比较；
然后考虑predecessor[i]之前的最小的斜率（即从 minSlopeStartIndexTable
[predecessor[i]] 到 predecessor[i]的斜率），如果比（predecessor[i] 到i 的斜率）要小
，那么他们合起来的斜率是一个比predecessor[i]到i的斜率更小的斜率。所以，我们用这个和
minSlope比较。
在以上比较进行完成之后，可以保证 minSlope 是从 0~i中所有可能中的最小斜率。
每次对 index i的比较需要 O(1)的时间，一共进行n次，所以也是O(n)的时间。
*****************************Test Case***************************************
另外，为了测试方便，给出Test Case：
（测试的人把code里面的freopen、结尾的while(1)取消注释就好了；同时建立测试文件
MaxSlopeOverInterval_in.txt，保存在和这个code的相同目录下）
[解决办法]
[解决办法]
好吧，我自己写个贴上来吧。
输入方式采用每行 ： 时间 分数， 输入至EOF。
- C/C++ code
#include <stdio.h>#include <string.h>#include <stdlib.h>#define MAXN 1000000double Calc(int Time[], int Score[], int N, int &Begin, int &End){ static int Next[MAXN]; int i, j; memset(Next, 0x7F, sizeof Next); for (i = 0, j = 1; i < N && j < N; ) { if (Score[j] - Score[i] >= 100) { Next[i] = j; ++i; } else { ++j; } } double Best = 0; Begin = End = -1; for (i = 0; i < N; ++i) { for (j = Next[i]; j < N && j < Next[Next[i]]; ++j) { double CurrentRes = (double)(Score[j] - Score[i]) / (double)(Time[j] - Time[i]); if (CurrentRes > Best) { Best = CurrentRes; Begin = i; End = j; } } } return Best;}int main(){ static int Time[MAXN]; static int Score[MAXN]; int N = 0; while (scanf("%d %d", &Time[N], &Score[N]) != EOF) { ++N; } int Begin, End; double Ans = Calc(Time, Score, N, Begin, End); printf("Begin = %d, End = %d, Ans = %.4lf\n", Begin, End, Ans);}
[解决办法]
恩，这个思路似乎是对的，首先每次迭代过程，斜率最大值递减，因此不存在后面找出的解优于前面的解，此外每次减少1个点，n*log(n)的复杂度也有保证。而且编程比较简单。不过感觉证明上还差一点点，就是如何保证用这种方法一定可以找出最优解。总的来讲是个很不错的思路。
[解决办法]
[解决办法]
@zy1072:感觉上我的算法和你的算法的理论基础应该是一样的，只是我是从前往后扫描，存储了一个之前的最优状态，所以达到了O(n)的时间。
不过，你的算法里面有个地方我没有理解（其实也是造成两个算法时间复杂度不同的地方）：
[Quote=引用:]
... ...
- C/C++ code
for (j = Next[i]; j < N && j < Next[Next[i]]; ++j)
[解决办法]
这应该不算反例，第一次取到第一段时间为0 - 1，该段同1-100合并（需要从队列中删除1-100这一段），把时间0 - 100放入，第2次则会取到100-101，此时再合并的话，应当是同0-100合并，而不是1-100合并，因为1-100已经同前段合并并删除了。
[解决办法]
[解决办法]
[解决办法]
用STL中的 multimap 实现了一个程序。
思路:
把每个时刻以及对应的分数存到链表中。
分别计算出所有相邻两个时刻间的得分效率。加入map。
从map中得到得分率最大时段m ，假设时段m的起始时刻为 b,结束时刻为c，显然b与c在链表中是相邻的。
若在时段m中已经得了100分，则找到了答案，退出。
否则,删除map中的时段m, 然后进行时段合并：
1。若链表中c的右面还一个时刻d 则在链表中删除c时刻，使b与d相邻，同时，删除map中以c时刻为起始时刻的时段，把b，d 时段的得分率加入map中
2。若链表中b的左面还一个时刻a 则在链表中删除b时刻，使a与c相邻，同时，删除map中以a时刻为起始时刻的时段，把a，c 时段的得分率加入map中.
这样做可以找到答案的原因是。
时刻为 [a,b,c,d,e,f,g] ，假设时段m=(d,e)得分率最高，若m的相邻时段包含在最终的结果中，则m也一定在最终的结果中。否则，不妨设最终结果是n=(b,d) ,显然n的得分率小于m的得分率，则把m与n和并后可得到得分率更高的时段，这与n是得分率最高的时段矛盾。
- C/C++ code
#include <iostream>#include <map>#include <list>using namespace std; #define N 10int score[] = {0, 5, 28, 71, 97, 105, 120, 181, 190, 201};int time[] = {0, 10, 30, 44, 99, 110, 125, 198, 203, 230};typedef list<pair< int, int> > LIST ; //list中保存每个时刻的一对score和time。typedef LIST::iterator LISTITER;typedef multimap< double, LISTITER > MAP; double GetRatio(LIST::iterator iter) //计算出链表中当前时刻到下一时刻的得分率{ LIST::iterator prev=iter++; double ret= (iter->first-prev->first)/double(iter->second-prev->second); return ret;}int GetCount(LIST::iterator iter) //计算出链表中当前时刻到下一时刻的总分数{ LIST::iterator prev=iter++; return iter->first - prev->first;}void erase(MAP & imap, MAP::key_type &key , MAP::mapped_type &value) //从imap中删除键位key,值为value的节点.{ for (MAP::iterator i=imap.lower_bound(key); i!=imap.upper_bound(key); ++i) if(i->second == value) { imap.erase(i); break; }}int main(){ LIST ilist; for (int i=0; i<10; ++i) { ilist.push_back(make_pair(score[i], time[i])); //初始化链表 } MAP imap; LISTITER iter=ilist.begin(); LISTITER prev=iter++; while ( iter !=ilist.end()) { imap.insert( make_pair(GetRatio(prev), prev)); //以得分率为键，以链表中的位置为值，加入到imap中 prev=iter++; } MAP::iterator iter_m; LISTITER iter_l; while (!imap.empty()) { iter_m=imap.begin(); //取出得分率最高的时段 iter_l=iter_m->second; //得到这个时段的起始时刻在链表中的位置 if (GetCount(iter_l)>=100) //如果这个时段已经得了100分以上，退出 { break; } imap.erase(iter_m); //从imap中移除iter_m //如果iter_l的右边至少有两个时刻，则去掉iter_l的右边的那个点，得到一个更大的时段 if(distance(iter_l,ilist.end())>2) { ++iter_l; double ratio=GetRatio(iter_l); erase(imap, ratio, iter_l); //去掉下一时段 LIST::iterator next = iter_l--; ilist.erase(next); //去掉下一时刻 imap.insert( make_pair(GetRatio(iter_l), iter_l)); //把合并后的时段加入imap } //否则，如果iter_l的左边至少有两个时刻，则去掉iter_l的左边的那个点，得到一个更大的时段 else if(distance(ilist.begin(), iter_l)>2) { --iter_l; double ratio=GetRatio(iter_l); erase(imap, ratio, iter_l); LIST::iterator next = iter_l--; ilist.erase(next); imap.insert( make_pair(GetRatio(iter_l), iter_l)); } } if(imap.empty()) { cout<<"总分数小于100"<<endl; } else { LIST::iterator prev=iter_l++; cout<<"开始时间:"<<prev->second<<endl; cout<<"结束时间"<<iter_l->second<<endl; cout<<"最大得分效率为"<<GetRatio(prev)<<endl; } }
[解决办法]
[解决办法]
[解决办法]
这个属于实现上的细节，至于怎么解决，你懂的，呵呵。