CodeForces - 1133C - Balanced Team

链接：https://codeforces.com/problemset/problem/1133/C

题意

一共有n个学生，你现在要从这些学生中选出几个人组一个队。要求一个队的学生中，任意两个学生会的技巧数相差不大于5，并且使这个队的学生数最大。输出这个最大学生数。

思路

先给n个学生的技巧数从小到大排序，用p表示一队里技巧数最小学生的下标，i表示该队技巧数最大学生的下标，则 i-p+1 为这个队的学生数量，比较每次 i-p+1 的值取最大那个就是最终结果。 关键代码如下：

for(i=1;i<n;i++) { while(a[i]-a[p]>5) p++; res=max(res,i-p+1); }

p的初始值取0，i初始值取1，当a[i]-a[p]>5时，p加一，即表示最小技巧数的学生的下标加一，继续比较。这样写的优势是两个下标一起增加，省去很多时间。

我一开始的想法是，先循环最小值找出对应满足要求的最大值，记录学生数，这样会做很多不必要的循环。

代码

#include<bits/stdc++.h> #include<algorithm> using namespace std; const int maxn=200005; int a[maxn]; int main() { int i,j,n,res=1,p=0; cin>>n; for(i=0;i<n;i++) cin>>a[i]; sort(a,a+n); for(i=1;i<n;i++) { while(a[i]-a[p]>5) p++; res=max(res,i-p+1); } cout<<res; return 0; }