牛客网OJ题解--20210221

主持人的烦恼

https://ac.nowcoder.com/acm/problem/13591

本系列记录翀翀😐痛苦的刷题日志，所有题目均来自于牛客网OJ题目，坚持刷题谈起来容易做起来难，希望我可以坚持下去，这里仍然分享一段励志文案：每个人都有梦想，然而有些人把梦想变成了现实，有些人的梦想依旧是梦想，只因为他们为梦想付出的努力程度不一样，他们坚持的时间不一样，最终才有这样的结果。

NC13591-主持人的烦恼

题目链接

https://ac.nowcoder.com/acm/problem/13591

题目描述

一天zzq主持一项游戏，共n位同学，需要两两同学为一组来上台来玩一项游戏。但是，众所周知，玩游戏的时候，如果两个人的颜值差距>=m，就会互相嫌弃。所以，为了游戏能够好玩。在游戏开始前，zzq已经调查了所有n个同学的颜值。但是现在问题又来了，zzq想知道，最多能凑出多少组同学一起上台？需注意一人只能出现在一个组中。多组输入第一行两个正整数n m（n<=1e5,m<=1e9），意义见描述第二行有n个由空格分开的正整xi（xi<=1e9），第i个同学的颜值。我们需要输出一个数表示最多可以组成多少个组合。

测试样例

输入

输出

2
1

说明

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

解题思路

贪心解决，我们将颜值从小到大排序，i和i+1检验能否组成一组，如果可以，那么i+2，即这两个人组成一组，i和i+1就不再参与组合选拔了，此时组数加一。如果i和i+1都不能组成一组，那么i++，即i没有可以组合的伙伴了，不参与选拔了，但是此时i+1还可以尝试选拔。

解题代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int ans = 0;
//存取学生的颜值
int s[N];

int main()
{
    int n, m;
    while (cin >> n >> m)
    {
        ans = 0;
        //每次都要初始化为全0
        memset(s, 0, sizeof(s));
        for (int i = 0; i < n; i++)
        {
            cin >> s[i];
        }
        //排序
        sort(s, s + n);
        for (int i = 0; i < n - 1;)
        {
            //当相邻的两个可以组合（最好情况了）
            if (s[i + 1] - s[i] < m)
            {
                //这两个人不再参与选拔
                i += 2;
                //组数加一
                ans++;
            }
            else
            {
                //没有人可以和他组合了，所以跳过他
                i++;
            }
        }
        cout << ans << endl;
    }
    system("pause");
    return 0;
}

NC13585-安卓图案解锁

题目链接

https://ac.nowcoder.com/acm/problem/13585

题目描述

栗主席(lizi)是某xxxx大学的一个不得了的程序猿，然而没想到吧，他竟然有女盆友，我们假设为QAQ！！！

那天，QAQ问栗子：你的小米5s的图像解锁密码到底是多少？

栗子：嘛？我仔细想想...

QAQ：你仿佛在逗我...

...

栗子：我的图像解锁用过好多次密码，后来都是用指纹解锁，所以忘记密码辣。但是我记得可能是那几个密码

QAQ：那你务必告诉我...

栗子: ...

然后，栗子就写下了一堆可能的密码，安卓图案解锁中，数字对应的位置已经标出。

但是栗子当然不想把真正的密码告诉QAQ，所以给QAQ的一系列的密码中，甚至有一些密码，是不符合安卓图案解锁的规则的。

QAQ也知道栗子肯定不老实，给了很多错的密码，甚至不符合规则的密码，所以想请你来找出，哪些密码是不符合规则的。

安卓图案解锁的密码有这样的一些特点：

1.每个数字最多只会被使用一次。

2.如果想直接连接两个数字，但是线段中会经过另一个数字，当且仅有那个数字已经在之前就被使用过了，才会合法。(比如你想从1直接连接到9，那么要么是1->3->9,要么是3在之前已经被使用过了，然后才能直接从1->9)。

多组输入，每组输入占一行，包含一串数字(1~9)，长度不超过30

输出这个安卓图案解锁是否合法，如果合法输出"YES",反之输出"NO" (请参照样例输出，不要输出引号)

测试样例

输入

输出

YES
NO
YES
NO

解题思路

我们需要将不能直接相连点的情况标记出来，如下：

1,3,7,9四个点不能直接相连，2,8不能直接相连，4,6不能直接相连，这三种情况都需要先保证他们的中间均值节点相连，如1和3的均值节点2被使用了，或者2,8均值节点5倍使用了才可以。对这三种不能直接相连点的情况赋予不同的标记权重值1(黄）,2（绿）,3（蓝）。所以我们需要逐位检验两个相邻的点，如果相等或者其中一个被使用过了，或者这两个点是不能直接相连的但是他们的中间均值点还没有使用过，那么这个密码就是不合法的。

解题代码

#include <bits/stdc++.h>
using namespace std;

int main()
{
    //标记数组，0表示未使用过，1表示使用过
    int vis[9] = {};
    //对不同的不能直接相连情况的点赋值不同的权重
    int pri[9] = {1, 2, 1, 3, 0, 3, 1, 2, 1};
    string s;
    while (cin >> s)
    {
        //默认都可以
        bool ok = true;
        //一定要初始化标记数组全0
        memset(vis, 0, sizeof(vis));
        //对每一个点逐一检验
        for (int i = 0; i < s.size() - 1; i++)
        {
            //两个相邻点的值
            int a = s[i] - '0';
            int b = s[i + 1] - '0';
            if (a == b)
            {
                //相邻两个点相同，如3321
                ok = false;
                break;
            }
            if (vis[a - 1] == 1 || vis[b - 1] == 1)
            {
                //或者当前点被使用过，如1232
                ok = false;
                break;
            }
            //标记这个点被使用过了
            vis[a - 1] = 1;
            //如果两个相邻点是不能直接相连的且他们中间节点还未使用过如139
            if (pri[a - 1] == pri[b - 1] && !vis[(a + b) / 2 - 1])
            {
                //那么不符合题干
                ok = false;
                break;
            }
        }
        if (ok)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    system("pause");
    return 0;
}