CodeForces - 1133C Balanced Team (队列

数据很大，用一点一点的dp思想做就爆内存了。

然后两天时间，没事就想想，没事就想想。想到了队列…
**que.sizeof( )**计算队列的大小，先把队员的能力值从小到大排序从最小的开始遍历，设置一个极值maxn用来计算该队员最大能力的队友。

即manx = a + 5;
然后到某个队友超出队友的范围，就q.pop(),然后判断下一个，如果还是无法与新来的组队，继续pop…直到容得下那个人，就算拿到队列为空…也要保证那个人能进入队列。

总而言之也是一种暴力的思想，不过队列可能会快一点吧，
我写的不是很好，空间复杂度也很高，但好歹做出来了…

下面是代码：

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;
int a[200020],cnt[200020];

queue<int> q;


int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> a[i];

    sort(a+1,a+1+n);

    int j = 0;
    q.push(a[1]); //能力最小的队员入队列了
    cnt[j] = q.size();
    int maxn = q.front()+5; //他能组的队友能力的极限

    for(int i = 2; i <= n; ++i)//从第二个开始遍历
    {


        if(a[i] <= maxn)//符合要求进入队列
        {
            q.push(a[i]);
            cnt[j] = q.size();
            continue;
        }

        else//不符合要求，把队首拿出，然后依次判断下面的队员
        {
            cnt[j++] = q.size();
            q.pop();
            while(!q.empty())
            {
                maxn = q.front()+5;
                if(a[i]>maxn)
                {
                    cnt[j++] = q.size();
                    q.pop();
                }
                else
                {
                    q.push(a[i]);
                    maxn = q.front()+5;
                    break;
                }
            }
            if(q.empty())//队列被拿空了，只能自己进去了
            {
                q.push(a[i]);
                maxn = q.front()+5;
            }
        }


    }
    int k = 0;
    for(int i = 0; i <= j; ++i)
        k = max(k,cnt[i]);

    cout << k << endl;
    return 0;
}