求双重循环对数组元素连续遍历的优化

输入N个数存到数组中，要求连续删除一段数字，至少删除一个数字，但第一个和最后一个数字不能删除，输出所有删法中剩下的数平均值的最小值。
下面程序当N较大时，运行会超时，想找到优化算法。3<=N<=100000
删掉的数字要求在数组中序号连续！
例如输入4 5 7 8 1，4表示数字个数，输出3.000，把7,8删掉。

#include<stdio.h>
int main()
{
    int N, i,k, a[111111];
    double x,y, min, sum = 0;
    scanf("%d", &N);
    for (i = 1; i <= N; i++)
    {
        scanf("%d", &a[i]);
        sum += a[i];
    }
    min = (sum - a[2]) / (N - 1);
    for (i = 2; i <= N - 1; i++)
    {
        x = sum;
        for (k = 0; k <= N - 1 - i; k++)
        {
            x = x - a[i + k];
            y = x / (N - k - 1);
            if (min > y)  min = y;
        }
    }
    printf("%.3lf", min);
    return 0;
}

假设 X 为 第N-1 个元素开始向前 m 个元素的集合，所求即为 (Sum(X) + a[0] + a[N-1]) / (m+2) 的最小值
所以只需要找到 Sum(X)/m 的最小值

double sum = 0;
int m = 0;
double min = DBL_MAX;
for(int i = N - 1, n = 1; i > 0; --i, ++n)
{
    sum += a[i];
    if(min > sum/n) {
        min = sum/n;
        m = n;
    }
}
printf("m = %d, min = %.3lf\n", m, min);

换了一种思路，你之前的要把所有删除方法都执行一边，我这个只执行部分。
思路：对除首尾的数据进行排序，初始ave=(a[0]+a[N-1])/2。从下标1开始循环，如果数组元素小于这个平均值，那么就不保留这个，并且重新计算平均值，一直到数组元素大于平均值，那么就执行删除操作，因为继续保留会导致平均值变大，因为是递增排序，所以后面的也不用保留，程序结束。
代码如下：

#include<stdio.h>
int main()
{
    int N, k, a[111111];
    double x, y;
    scanf_s("%d", &N);
    for (int i = 0; i < N; i++)
    {
        scanf_s("%d", &a[i]);
    }
    for(int i=1;i<N-2;i++)         //对除首尾的数据排序
        for(int j=1;j<N-2-i;j++)
            if (a[j] > a[j + 1])
            {
                int temp;
                temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
    double sum= (double)a[0] + a[N - 1], ave = sum/2;
    for (int i = 1; i < N - 2; i++)
        if (a[i] < ave)
        {
            sum += a[i];
            ave = sum / ((double)2 + i);
        }
        else
            break;
    
    printf("%.3lf", ave);
    return 0;
}

我问个问题，连续删除是出现在数组中位置的连续，而不是排序的连续吧，上面那些回答好像都是认成了排序的连续

刚刚没考虑最少删一个
看看现在这个能过不

#include<stdio.h>
#include<stdlib.h>
int count=2;
void QuickSort(float t[],int Begin,int End)
{
    if(Begin>=End) return;
    int Left=Begin,Right=End;
    float tem=t[Begin];
    while(Begin<End)
    {
        while(Begin<End&&t[End]>=tem)
        {
            End--;
        }
        t[Begin]=t[End];
        while(Begin<End&&t[Begin]<=tem)
        {
            Begin++;
        }
        t[End]=t[Begin];
    }
    t[Begin]=tem;
    QuickSort(t,Left,Begin-1);
    QuickSort(t,Begin+1,Right);
}
float cacluave(float t[],int pn,float base)
{
    float sum=0;
    count=2;
    for(int i=1; i<=pn; i++)
    {
            sum+=t[i];
            count++;
    }
    return (sum+base)/count;
}
void randnum(float t[],int n)
{
    for(int i=0; i<n; i++)
    {
        t[i]=rand()%n;
    }
}
int main()
{
    float t[100000];
    int n;
    scanf("%d",&n);
    //randnum(t,n);
    for(int i=0; i<n; i++)
        scanf("%f",&t[i]);
    
    float base=t[0]+t[n-1];
    QuickSort(t,1,n-2); 
    float min=(t[1]+base)/2;
    int pos=0;
    for(int i=n-2; i>=1; i--)
    {
        float tem=cacluave(t,i,base);
        if(tem<min)
        {
            min=tem;
            pos=count;
            //printf("%d",count);
        }
    }
    if(pos==n)
    {
        min=cacluave(t,n-3,base);
    }
    printf("%.3f",min);
    return 0;
}

假设这个数组的数字是这样一个串

其中第一个方格和最后一个根据题目要求，需要舍弃

□□□□...□□□□ 变成 □□□...□□□

然后对这个的每一个格子命名为1,2,3,4,5,6

设c[i]表示所有的求和方法中,第i个数被加的次数

比如n=5，每个数的值不用管，

c数组的计算：

用类似的方法对更大的数进行计算，然后用一个for循环求和再除以方案数（组合数）

总共是常数个一次

复杂度O(N)

代码后面有空就写

你得用全局变量，修改成这样试试

#include<stdio.h>
 int N, i,k, a[111111];
double x,y, min, sum = 0;
int main()
{

    scanf("%d", &N);
    for (i = 1; i <= N; i++)
    {
        scanf("%d", &a[i]);
        sum += a[i];
    }
    min = (sum - a[2]) / (N - 1);
    for (i = 2; i <= N - 1; i++)
    {
        x = sum;
        for (k = 0; k <= N - 1 - i; k++)
        {
            x = x - a[i + k];
            y = x / (N - k - 1);
            if (min > y)  min = y;
        }
    }
    printf("%.3lf", min);
    return 0;
}