首页 > 代码库 > NYOJ 847 S + T

NYOJ 847 S + T

S + T

时间限制:1000 ms  |  内存限制:65535 KB
难度:2
描述

   给你一个长度为n的整数序列A1,A2,……,An,找出两个整数Ai和Aj(i<j),使得Ai-Aj尽量大。

输入
输入第一行为数据组数T(T<=100)。每组数据的第一行为整数的个数n(2<=n<=100000);一下n行,每行为一个绝对值不超过150000的正整数。(所有的数据都不超过2^64 - 1)
输出
对于每组数据,输出Ai –Aj的最大值、i值和j值。(如果有多个最大值,则输出先出现的最大值和i,j值)
样例输入
2
3
5 2 1
6
2 3 6 2 1 -1
样例输出
4 1 3
7 3 6
提示

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

AC码:

#include<stdio.h>
struct node
{
	long long m;
	long long c;
}min[100005];
long long num[100005];
int main()
{
	long long n,T,i,max,x,y;
	scanf("%lld",&T);
	while(T--)
	{
		scanf("%lld",&n);
		for(i=1;i<=n;i++)
			scanf("%lld",&num[i]);
		min[n].m=num[n];
		min[n].c=n;
		for(i=n-1;i>=1;i--)
		{
			if(num[i]<=min[i+1].m)  // 这错了一次,没写=
			{
				min[i].m=num[i];
				min[i].c=i;
			}
			else
			{
				min[i].m=min[i+1].m;
				min[i].c=min[i+1].c;
			}
		}
		max=-200000;   // 这错了一次,赋了0
		x=0;
		y=0;
		for(i=1;i<n;i++)
		{
			if(num[i]-min[i+1].m>max)
			{
				max=num[i]-min[i+1].m;
				x=i;
				y=min[i+1].c;
			}
		}
		printf("%lld %lld %lld\n",max,x,y);
	}
	return 0;
}