欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

主持人的烦恼——贪心

程序员文章站 2023-12-29 17:16:34
链接:https://ac.nowcoder.com/acm/problem/13591来源:牛客网题目描述一天zzq主持一项游戏,共n位同学,需要两两同学为一组来上台来玩一项游戏。但是,众所周知,玩游戏的时候,如果两个人的颜值差距>=m,就会互相嫌弃。所以,为了游戏能够好玩。在游戏开始前,zzq已经调查了所有n个同学的颜值。但是现在问题又来了,zzq想知道,最多能凑出多少组同学一起上台?需注意一人只能出现在一个组中。输入描述:多组输入第一行两个正整数n m(....

链接:https://ac.nowcoder.com/acm/problem/13591
来源:牛客网
 

题目描述

一天zzq主持一项游戏,共n位同学,需要两两同学为一组来上台来玩一项游戏。

但是,众所周知,玩游戏的时候,如果两个人的颜值差距>=m,就会互相嫌弃。

所以,为了游戏能够好玩。在游戏开始前,zzq已经调查了所有n个同学的颜值。

但是现在问题又来了,zzq想知道,最多能凑出多少组同学一起上台?

需注意一人只能出现在一个组中。

输入描述:

多组输入
第一行两个正整数n m(n<=1e5,m<=1e9),意义见描述
第二行有n个由空格分开的正整数xi(xi<=1e9),第i个同学的颜值

输出描述:

每一行输出一个数,表示最多能凑出多少组。

示例1

输入

复制4 3 1 3 3 2 4 2 1 4 6 2

4 3
1 3 3 2
4 2
1 4 6 2

输出

复制2 1

2
1

说明

第二组样例中,编号为1的同学(颜值是1)与编号为4的同学(颜值是2),颜值差距为1,可以组成一组

思路

对于这种跟差值有关的贪心题目,感觉通常都要排序。所以先排个序,而且当1号和2号的差距大于m时,1号和3号必然也大于m,当1、2、3号之间的差距都小于m时,当然优先让1、2组队。因为万一3、4差距小于m,然后1、3组了,但是2、4差距大于m,这不就少组了一组吗。所以只要i号能跟i+1号组,那么就马上把他们组了就好了。

代码

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

int main(){
    int n,m,z[100005];
    while(cin>>n>>m){
        for(int i=0;i<n;i++){
            cin>>z[i];
        }
        sort(z,z+n);
        int count=0;
        for(int i=1;i<n;i++){
            if(z[i]-z[i-1]<m){
                count++;
                i++;
            }
        }
        cout << count<<endl;
    }
    return 0;
}

 

 

本文地址:https://blog.csdn.net/weixin_41753316/article/details/107884653

上一篇:

下一篇: