算法知识点:多组输入、排序、贪心算法

解题思路

首先将所有人的颜值从小到大排序,如果a【1】和a【2】不能组队,那么a【1】肯定和a【3】不能组队。所以第一个人没有必要去找后边的人去组队,因为假设第一个人和第三个人组了队,兴许之后的第四个人就再没有组队的机会了。所以我们直接按照相邻的两个人组队去做即可。
1.实现多组输入 while(cin>>n>>m)
2.在while循环中嵌套for循环n次,依次获取n个学生的颜值,存入数组a[]
3.数组a从小到大排序
4.贪心算法:依次比较相邻两元素之差,如果可组队,数组下标j前进2,组队数+1,否则数组下标j前进1
5.输出组队数
注:多组输入的n、m不同,所以数组a[]的有效长度存在变化,因此将数组a的声明和组对数count的声明及初始化放在while循环中

#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
    int n,m;//n表示人数,m表示颜值差上限
    while(cin>>n>>m)
    {
        int a[n];//存放每个学生的颜值
        int count=0;//表示组队数,初始为0
        //依次获取每个人的颜值
        for (int i = 0; i < n; ++i)
        {
            cin>>a[i];
        }
        //排序
        sort(a,a+n);
        //贪心算法
        for (int j = 0; j < n-1; )
        {
            if(a[j+1]-a[j]<m)//组队成功
            {
                j+=2;
                count++;
            }
            else//组队失败
            {
                j++;
            }

        }
        //输出组队数
        cout<<count<<endl;
    }
    return 0;
}