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; // 這錯了一次，賦了0x=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; }

總結

以上是生活随笔為你收集整理的NYOJ 847 S + T的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。