HDU 5328 Problem Killer(2015多校联合)

发表于   |  

题目链接

戳我

题目大意

一个序列 $a$, 求这个序列的 连续子序列 中最长的等差序列或者等比序列

样例解释

2 // T
5 //n
1 2 3 4 6 //n个数, 1,2,3,4是最长等差序列,长度为4
10 //n
1 1 1 1 1 1 2 3 4 5 //前6个1满足等差(比)序列,且长度最长是6

解题思路

暴力查询即可
此题坑点: 等比序列 的 公比 可能时 分数.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
//Author LJH
//www.cnblogs.com/tenlee
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#define clc(a, b) memset(a, b, sizeof(a))
using namespace std;

const int inf = 0x3f;
const int INF = 0x3f3f3f3f;
const int maxn = 1e6+5;
const double eps = 1e-6;

int n;
double a[maxn];

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        for(int i = 0; i < n; i++) 
        {
            scanf("%lf", &a[i]);
        }
        double ap = a[1] - a[0];
        double gp = a[1] / a[0];
        int len1 = 1, len2 = 1;
        int malen1 = 1, malen2 = 1;
        for(int i = 1; i < n; i++)
        {
            if(abs(a[i] - a[i-1] - ap) < eps) len1++;
            else
            {
                ap = a[i] - a[i-1];
                len1 = 2;
            }
            malen1 = (malen1 > len1 ? malen1 : len1);

            if(abs(a[i] / a[i-1] - gp) < eps) len2++;
            else
            {
                gp = a[i] / a[i-1];
                len2 = 2;
            }
            malen2 = (malen2 > len2 ? malen2 : len2);
        }
        printf("%d\n", malen1 > malen2 ? malen1 : malen2);
    }
    return 0;
}