CF 1133C Balanced Team

题目链接：http://codeforces.com/problemset/problem/1133/C

题目分析

（个人感受：我看错了题目，硬是写了近一个小时！）

这个题目要求一个最长的序列，使得这个序列的每一个数之间的差值的绝对值都小于或等于5。

想到求序列中的数的差值的问题，我在想，如果这个序列是单调递增的，那岂不是直接用序列尾部取和头部比较，如果差小于等于5，那么这个序列是满足条件的。

而我们需要找出所有的这样的序列的最长者，我有个大胆的想法，如果题目给出的序列a[]就是单调递增的，当我们用s代表当前序列的左边界，e代表右边界，那么如果a[e+1] - a[s] <= 5 ，那么我们就可以将e+1拉入这个序列，从而实现右边界向右扩展以得到新的合法序列；

因为 a[x+1] >= a[x] (就是因为是单调递增序列) , 如果a[e+1] - a[s] <= 5 ，那么对于区间[s,e]的任意一个数x都有a[e+1]>=a[x] , 所以序列[s,e+1]是符合条件的序列之一；

我们用 len 记录这些合法序列中的最长者（我之前以为需要找到整体的skill值最高的序列的长度，结果上演了和评测机大战了数个回合，终以我的失败而告终的一段经典！）。

在每次将右边界向右扩展的时候，当前序列的长度会增加，这样我们就需要比较当前序列和len的大小了.

如果a[e+1] - a[s] > 5 ，那么也很好办，之所以会出现这个情况，就是因为左边界s太小了，我们只需要将左区间向右移动一个位置，然后再去和a[e+1]比较，其差值一定小于等于之前的差值；同时这个序列新序列[s+1,e]肯定是合法的(不用解释了吧）；当然，如果当前的s == e ，我们需要同时将右边界向右移动一个位置。

我们将区间[s,e]从[1,1]开始不断地向右扩展，这样就可以得到所有合法序列了，不过记得对题目给的序列排个序嗯。

代码区

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include <vector>

#include<stack>

using namespace std;

typedef long long ll;

const int inf = 0x3f3f3f3f;

const int Max = 2e5 + ;

const int mod = 1e9 + ;

ll a[Max];

int main()

{

    ll n;

    while (scanf("%I64d", &n) != EOF)

    {

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

        {

            scanf("%I64d", a + i);

        }

        sort(a + , a +  + n);

        ll s = ;

        ll e = ;        //[s,e]表示当前区间

        ll len = ;        //整个最长

        while (e < n)

        {

            //cout << "[ " << s << " , " << e << " ]" << endl;

            if (a[e + ] - a[s] <= )

            {

                ++e;        //区间[s,e] --> [s,e+1]，now + a[e+1]

                len = max(len, e - s + );

            }

            else

            {

                if (s == e)

                {

                    s = ++e;

                }

                else

                {

                    s++;

                }

            }

        }

        printf("%I64d\n", len);

    }

    return ;

}

巴特西

CF 1133C Balanced Team

题目分析

代码区

最新文章

热门文章