HDU 5328 Problem Killer（水题）

题意：

　　给一个序列，要找一个等差或等比的连续子序列，求其最长的长度。

思路：

　　扫两遍，判断等差或等比即可。从左往右扫，维护一个滑动窗口，考虑新加进来的数，如果满足了要求，则更新长度，否则只留最后两个数字，其他删掉，接着继续考虑下一个数字。等比也是如此，只是要注意精度的问题。

　　别人的代码：

 #include <bits/stdc++.h>

 using namespace std;

 const int MAX = 1e6+;

 int arr[MAX];

 int main(void)

 {

     //freopen("in.txt", "r", stdin);

     int t = ;

     scanf("%d", &t);

     while(t--)

     {

         int n = ;

         scanf("%d", &n);

         for(int i=; i<=n; ++i)

         {

             scanf("%d", &arr[i]);

         }

         if (n== || n==)

         {

             printf("%d\n", n);

             continue;

         }

         int l, r;

         l = ;

         int diff = arr[]-arr[];

         int ans1 = ;

         for(r=; r<=n; ++r)

         {

             if (arr[r] - arr[r-] != diff)

             {

                 diff = arr[r]-arr[r-];

                 l = r-;

             }

             ans1 = max(ans1, r-l+);

         }

         l=;

         double ddiff = 1.0*arr[]/arr[];

         int ans2 = ;

         for(r=; r<=n; ++r)

         {

             if ( fabs( 1.0*arr[r]/arr[r-] - ddiff) > 0.000001)

             {

                 ddiff = 1.0*arr[r]/arr[r-];

                 l = r-;

             }

             ans2 = max(ans2, r-l+);

         }

         printf("%d\n", max(ans1, ans2));

     }

     return ;

 }

AC代码

巴特西

HDU 5328 Problem Killer（水题）

最新文章

热门文章