杭電ACM HDU 1594 find the max

find the max

Time Limit: 1000/1500 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 496    Accepted Submission(s): 228

Problem Description 有一個離散函數f(x),x = {1, 2, ,,,,N}，f(x)<2^31。現在要找出2個點i,j, 使得函數在這2點之間的點都在這2點連線下方，且此連線的斜率的絕對值越大越好。

Input 輸入包括多個測試執行個體。每個測試執行個體包括2行，第一行為一個整數N，2 <= N <= 100000, 然後是N個整數f(x),x=1,2...N，讀到檔案結束符為止.

Output 對于每個測試執行個體輸出找到的i和j,如果有多個答案，輸出字典序最小的一個。

Sample Input

3
1 2 3
3
2 6 4
        

Sample Output

1 2
1 2


   
    
     Hint
    Hint
   
    
use scanf to avoid Time Limit Exceeded
        

Author 8600

Source HDU 2007-Spring Programming Contest - Warm Up （1）

Recommend 8600

#include <stdio.h>
#define abs(x) (x>0?x:-(x))
int main(){
    int n,a,b,p,m,i;
    while(~scanf("%d",&n)){
        scanf("%d",&a);
        m=0;
        for(i=1;i<n;i++){
            scanf("%d",&b);
            if(m<abs(a-b)){
                m=abs(a-b);
                p=i;
            }
            a=b;
        }
        printf("%d %d\n",p,p+1);
    }
}