算法知识点:多组输入、排序、贪心算法
解题思路
首先将所有人的颜值从小到大排序,如果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; }