?

S + T

给你一个长度为n的整数序列A1，A2，……,An,找出两个整数Ai和Aj(i

235 2 162 3 6 2 1 -1

4 1 37 3 6

?

?

#include 
  
   
#define maxn 100000 + 2
long long arr[maxn], ans, temp;
struct Node{
	long long val;
	int at;
} min[maxn]; //存储下标i到n的最小值和其下标

int main(){
	int t, n, x, y;
	scanf("%d", &t);
	while(t--){
		scanf("%d", &n);
		for(int i = 1; i <= n; ++i)
			scanf("%lld", arr + i);
			
		min[n].val = arr[n];
		min[n].at = n;
		
		for(int i = n - 1; i; --i){
			if(arr[i] <= min[i+1].val){
				min[i].val = arr[i];
				min[i].at = i;
			}else min[i] = min[i+1];
		}
		
		ans = arr[1] - arr[2];
		x = 1; y = 2; temp = arr[1] - 1;
		
		for(int i = 1; i < n; ++i){
			if(arr[i] > temp){
				temp = arr[i];
				if(temp - min[i+1].val > ans){
					ans = temp - min[i+1].val;
					x = i; y = min[i+1].at;
				}
			}
		}
		
		printf("%lld %d %d\n", ans, x, y);
	}
	return 0;
}
  

?

?

之前的一个TLE代码：

?

#include 
  
   
#include 
   
     #define maxn 100002 using std::min_element; long long arr[maxn]; struct Node{ long long ans; int i, j; } node, temp; int main(){ int t, n; long long *p; scanf("%d", &t); while(t--){ scanf("%d", &n); for(int i = 1; i <= n; ++i) scanf("%lld", arr + i); node.ans = arr[1] - arr[2]; node.i = 1; node.j = 2; temp = node; for(int i = 1; i < n; ++i){ if(arr[i] > arr[temp.i]) temp.i = i; p = min_element(arr + i + 1, arr + n + 1); if(arr[temp.i] - *p > node.ans){ node.ans = arr[temp.i] - *p; node.i = temp.i; node.j = p - arr; } } printf("%lld %d %d\n", node.ans, node.i, node.j); } return 0; } 
   
  

?

这题可能还有一个O（N）的算法，明天再想想看能不能找出来，现在已经2014-6-10 00:31:15了，该睡觉了。

描述

输入输入第一行为数据组数T（T<=100）。每组数据的第一行为整数的个数n(2<=n<=100000)；一下n行，每行为一个绝对值不超过150000的正整数。(所有的数据都不超过2^64 - 1)

输出对于每组数据，输出Ai –Aj的最大值、i值和j值。（如果有多个最大值，则输出先出现的最大值和i,j值）

样例输入

样例输出

提示如果你认为数据太大，则本OJ推荐使用long long