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


京公网安备 11010502036488号