Question

高分求一道ACM编程题：一道我自己超时的题，求大神说一下思路，比较水的题

题目基本描述是这样的
给你多组数据
第一行两个数N M
然后接下来N行数 代表代表1-N号选手得分
再接下来M行 每行两个数m1,m2 输出m2号选手和m1号选手之间所有选手的得分相差最大值
比如
6 3
1
5
6
3
7
8
1 3
5 5
2 4
输出
5
0
3

Answer 1

采用动态规划来做吧。
假设a[0]=1,a[1]=5,a[2]=6,a[3]=3,a[4]=7,a[5]=8
d[i][j]表示a[i][j]之间的最大分差
可见d[0][0]=d[1][1]=...=d[5][5]=0
d[0][1]=4
d[1][2]=1
d[2][3]=3
d[3][4]=4
d[4][5]=1
下面就是动态规划的递推方程了。为：
d[i][j]=max{d[i][j-1], d[i+1][j], abs(a[i] - a[j]) }
比如d[0][2] = max{ d[0][1], d[1][2], abs(1 - 6) } = max {4, 1, 5} = 5
使用这种方式计算出任意两个点之间的d[i][j]。
然后就读取输入，直接输出结果就好了。

Answer 2

#include<stdio.h>
void main()
{
int data[100],totol[100],N,M,i,j,left,right,max,min;
scanf("%d%d",&N,&M);
for(i=0;i<N;i++)
scanf("%d",&data[i]);
for(i=0;i<M;i++)
{
scanf("%d%d",&left,&right);
left-=1;
right-=1;
for(j=left;j<=right;j++)
if(j==left) {min=max=data[left];}
else
{
if(max<data[j]) max=data[j];
if(min>data[j]) min=data[j];
}
max=max-min;
totol[i]=max;
}
for(i=0;i<M;i++)
printf("%d\n",totol[i]);
}

Answer 3

# include<stdio.h>
# include <math.h>
# define M 100
void findmax(int * a,int m1,int m2)
{
    int i,j,k = 0,max,s[M];
    //用双层for循环将所有输入的数据相互作差，并取绝对值
    for(i = m1-1;i <= m2-1 ;i++)
        for(j = m1-1;j <= m2-1;j++)
        s[k++] = fabs(a[j] - a[i]);
    //找出最大的差
    max = s[0];
    for(i = 0;i < k ;i++)
    {
        if(s[i] > max)
            max = s[i];
    }
    printf("%d\n",max);
}
int main(void)
{
    int i,j,m,n,m1,m2,a[M];
    while(scanf("%d%d",&m,&n) != EOF)//可以连续测试多组数据，按crt + z作为结束标志
    {
        for(i = 0;i < m;i++)
            scanf("%d",&a[i]);
        for(j = 0;j < n;j++)
        {
            scanf("%d%d",&m1,&m2);
            findmax(a,m1,m2);//找出最大的差值
        }
    }
       
    return 0;
}

Answer 4

..不懂、、、、