2015 HDU 多校联赛 5328 Problem Killer

分类：ACM

题目：?pid=5328

这道题目主要是求构成等差或是等比的连续区间的最大长度，数据有可能是递增，也有可能是递减的，定义 l,r， r不停地往后移动，当不满足的时候就重新定义等差或是等比值，更新l, 每次更新区间大小的最大值即可，，要注意的主要是求等比的时候，浮点数的比较。（做多校的时候，多谢队友的提醒，这真是一个神队友 ^_^ ）

例如数据：13 5 2，如果没有转换为浮点数，那么答案为3是错误的。

// 求连续区间的最大等差长度或等比数列长度#include <bits/stdc++.h>using namespace std;const int MAX = 1e6+2;int arr[MAX] = {};int main(void){//freopen("in.txt", "r", stdin);int t = 0;scanf("%d", &t);while(t–){int n = 0;scanf("%d", &n);for(int i=1; i<=n; ++i){scanf("%d", &arr[i]);}// 特殊处理if (n==1 || n==2){printf("%d\n", n);continue;}// 等差int l = 1;int r = 1;int ans1 = 2;int diff = arr[2] – arr[1];for(r=3; r<=n; ++r){if (arr[r] – arr[r-1] != diff){diff = arr[r]-arr[r-1]; // 更新l = r-1;// 移动}ans1 = max(ans1, r-l+1);}//printf("ans1: %d\n", ans1);// 等比l = 1;r = 2;double dist = 1.0*arr[r]/arr[l];int ans2 = 2;for(r=3; r<=n; ++r){if ( fabs(1.0*arr[r]/arr[r-1] – dist) > 0.000001){dist = 1.0*arr[r]/arr[r-1];l = r-1; // 移动}ans2 = max(ans2, r-l+1);}//printf("ans2: %d\n", ans2);printf("%d\n", max(ans1, ans2));}return 0;}// 浮点数的比较// fabs(a-b) <= 0.000001 表示两者相等

// 浮点数的比较，fabs(a-b) <= 0.000001 表示两者相等

上一篇HDU 2069 Coin Change 母函数求解下一篇关于 ACM 的一点感想

顶1踩1

生活若剥去了理想、梦想、幻想，那生命便只是一堆空架子

相关文章：

你感兴趣的文章：

标签云：