由积分排行想到的一道算法题目《欢迎大家求解》
比如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吗？如果是这样的话，楼主给出的那个示例数据中，是不是没有一个符合这个条件的？
请解释。
[解决办法]
领进 = 临近
[解决办法]
#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.两指针都不能动了，那么最高的效率段就出来了
[解决办法]
注意，我所说的平均斜率是两个指针之间那一段的平均斜率
[解决办法]
#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)的复杂度也有保证。而且编程比较简单。不过感觉证明上还差一点点，就是如何保证用这种方法一定可以找出最优解。总的来讲是个很不错的思路。
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已经同前段合并并删除了。
#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; } }
[解决办法]