使用C语言。
在做OJ题的时候，在一道题目上的被难住了，花了很多时间去优化算法，还是出现了TLE。
《下面是题目。》
我最初对题目的理解：
- 给定一个N长度(接近10^5)的整数数列，其连续子数列可以含有1~N个元素。
- Lenth值就是子数列的元素个数。
- Weight值就是子数列的Lenth × 最小元素。
我起初的解法是：
- 用int N[100001]存储数列值，其中N[0]记录数列长度。
- AskWay 1 ：对于每次询问AskValue，使用三个嵌套循环，外循环为子数列长度从AskValue递增到N[0]，内循环为依次遍历整个数组，第二个内循环取子数列中间的最小值。将上述值依次暂存后，遇大的Weight就替换。得到目标结果。
- AskWay 2 ：对于每次询问AskValue，子数列长度从1开始递增，当Weight值大于AskValue时离开循环。
其结果不可避免的TLE超时了。
。
第二次想到，对于每个数列的Ｍ次询问，我只需要把该数列的每个长度的子序列Weight最大值存下来，然后每次询问只需要进行一次二分查找即可。
于是我再建立了MaxWeigth数组和MinLenth数组。
结果还是TLE。
。
第三次打算对数列的处理进行优化，想到长子序列一定包含短子序列，对于所有长子序列的最小值必定包含在所有短子序列的最小值中。
而且，假定子数列长度为“n”，数列总长度为“N”，则长度为n的连续子数列个数为N-n+1。
长度为n的两个相邻连续子数列的总长度为n+1(包含重复数列)，
则长度为n+1的长连续子数列必定包含两个相邻短连续子数列，其最小值在短数列的两个最小值中产生。
。
可以得到下图的结论。
比较次数为：n(n-1)/2。复杂度降为n^2。
结果还是TLE超时。VS测出单次建立持续时间为3600ms,而题目可能会测试T=15次。最后把数组用指针地址递增读取，持续时间降到了1400ms，然而还是不行。
以下为所用代码。
（写代码的时候为了便于测试，输入的N组数据用了随机数的方式读取，输出函数给注释掉了）
#include<stdio.h>
#include<stdlib.h>
#define Min(x) (((*x)<(*(x+1)))?(*x):(*(x+1)))
#define Wide 100001
int N[2][Wide] = { 0 };
int Len[Wide] = { 0 };
int MaxW[Wide] = { 0 };
int MinL[Wide] = { 0 };
void SubSequenceMax(void);
int BinarySearch(int a[], int value, int n);
int main()
{
int T, M;
int i, j, k, l, Askway, AskValue, weight, lenth;
//scanf_s("%d", &T);
T = 1;
for (i = 1; i <= T; i++)
{
//scanf_s("%d%d", &N[0][0], &M);
N[0][0] = 80000;
M = 40000;
for (j = 1; j <= N[0][0]; j++)
{
//scanf_s("%d", &N[0][j]);
N[0][j] = rand() % 100000;
}
;
SubSequenceMax();
;
MaxW[N[0][0]] = Len[N[0][0]];
MinL[1] = Len[1];
for (l = N[0][0] - 1; l >= 1; l--)
{
MaxW[l] = MaxW[l + 1] > Len[l] ? MaxW[l + 1] : Len[l];
MinL[N[0][0] + 1 - l] = Len[N[0][0] + 1 - l] < MinL[N[0][0] - l] ? MinL[N[0][0] - l] : Len[N[0][0] + 1 - l];
}
for (k = 1; k <= M; k++)
{
//scanf_s("%d%d", &Askway, &AskValue);
Askway = rand() % 2 + 1;//delete
if (Askway == 1)
{
AskValue = rand() % (N[0][0] / 2) + N[0][0] / 4;//delete
weight = MaxW[AskValue];
//printf("%d\n", weight);
}
else if (Askway == 2)
{
AskValue =Len[rand() % (N[0][0] / 2) + N[0][0] / 4];//delete
if (AskValue > MinL[N[0][0]]);// printf("-1\n");
else if (AskValue <= MinL[1]);// printf("1\n");
else
{
lenth = BinarySearch(MinL, AskValue, N[0][0]);
//printf("%d\n", lenth);
}
}
}
}
}
void SubSequenceMax(void)
{
int sublenth, record = 0, tempmax;
int *pN,*ipN;
int *rand;
for (sublenth = 1; sublenth <= N[0][0]; sublenth++)
{
if (record == 0)
{
pN = N[1];
ipN = N[0];
rand = &N[1][(N[0][0] - sublenth)+1];
record = 1;
pN++;
ipN++;
tempmax = N[0][1];
for (; pN <= rand; pN++, ipN++)
{
*pN = Min(ipN);
tempmax = (((*ipN * sublenth) > (tempmax * sublenth)) ? *ipN : tempmax);
}
Len[sublenth] = tempmax * sublenth;
}
else
{
pN = N[0];
ipN = N[1];
record = 0;
rand = &N[0][(N[0][0] - sublenth)+1];
pN++;
ipN++;
tempmax = N[1][1];
for (; pN <= rand; pN++,ipN++)
{
*pN = Min(ipN);
tempmax = (((*ipN * sublenth) > (tempmax * sublenth)) ? *ipN : tempmax);
}
Len[sublenth] = tempmax * sublenth;
}
}
}
int BinarySearch(int a[], int value, int n)
{
int low, high, mid;
low = 1;
high = n;
while (low <= high)
{
mid = (low + high) / 2;
if (a[mid] >= value && a[mid-1]<value)
return mid;
if (a[mid] >= value)
high = mid - 1;
if (a[mid] < value)
low = mid + 1;
}
return -1;
}
