首页 > ACM题库 > HDU-杭电 > HDU 1594 find the max[解题报告] C++
2013
12-12

HDU 1594 find the max[解题报告] C++

find the max

问题描述 :

有一个离散函数f(x),x = {1, 2, ,,,,N},f(x)<2^31。现在要找出2个点i,j, 使得函数在这2点之间的点都在这2点连线下方,且此连线的斜率的绝对值越大越好。

输入:

输入包括多个测试实例。每个测试实例包括2行,第一行为一个整数N,2 <= N <= 100000, 然后是N个整数f(x),x=1,2…N,读到文件结束符为止.

输出:

对于每个测试实例输出找到的i和j,如果有多个答案,输出字典序最小的一个。

样例输入:

3
1 2 3
3
2 6 4

样例输出:

1 2
1 2

Hint
Hint
use scanf to avoid Time Limit Exceeded

其实挺水的,就是找出相邻的点中斜率绝对值最大的。因为没细看题目,忘了是“绝对值”,WA了两次,杯具。。。

/*
 * hdu1594/win.cpp
 * Created on: 2012-7-23
 * Author    : ben
 */
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <functional>
#include <numeric>
#include <cctype>
using namespace std;
const int MAXN = 100010;
int n[MAXN], d[MAXN];

int main() {
#ifndef ONLINE_JUDGE
    freopen("data.in", "r", stdin);
#endif
    int T;
    while(scanf("%d", &T) == 1) {
        for(int i = 0; i < T; i++) {
            scanf("%d", &n[i]);
        }
        for(int i = 1; i < T; i++) {
            d[i] = abs(n[i] - n[i - 1]);
        }
        int ans = -1, ansj;
        for(int i = T - 1; i > 0; i--) {
            if(d[i] >= ans) {
                ans = d[i];
                ansj = i;
            }
        }
        printf("%d %d\n", ansj, ansj + 1);
    }
    return 0;
}

解题报告转自:http://www.cnblogs.com/moonbay/archive/2012/07/23/2605437.html


  1. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥