华东交通大学2017年ACM“双基”程序设计竞赛 1008

Problem Description

长度为 n 的序列，把它划分成两段非空的子序列，定义权值为：两段子序列的最大值的差的绝对值。求可能的最大的权值。
数据范围：
2 <= n <= 10^6 ， 0 < 序列内的数 <= 10^6 。

Input

第一行输入一个 T，表示有　T　组数据。
接下来有 T 组数据，每组数据的第一行输入一个数 n ，第二行输入 n 个数。

Output

每组数据输出可能的最大的权值。

Sample Input

Sample Output

2

解法：暴...暴力

 #include<bits/stdc++.h>

 using namespace std;

 int cnt[];

 int Max_a[];

 int Max_b[];

 int Min=;

 int main(){

     int t,n;

     scanf("%d", &t);

     while(t--){

         Min=;

         memset(Max_a, , sizeof(Max_a));

         memset(Max_b, , sizeof(Max_b));

         scanf("%d",&n);

         for(int i = ; i <= n; i++){

             scanf("%d", &cnt[i]);

             Max_a[i] = max(Max_a[i - ], cnt[i]);

         }

         for(int i = n; i > ; i--){

             Max_b[i] = max(Max_b[i + ], cnt[i]);

         }

         for(int i = ; i < n; i++){

             Min = max(Min, abs(Max_a[i] - Max_b[i + ]));

         }

         printf("%d\n", Min);

     }

     return ;

 }

巴特西

华东交通大学2017年ACM“双基”程序设计竞赛 1008

Problem Description

Input

Output

Sample Input

Sample Output

最新文章

热门文章