牛客网OJ题解--20210220

牛兄牛弟

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

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

NC21781-牛兄牛弟

题目链接

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

题目描述

一群牛兄牛弟准备去一家餐厅吃饭，已知他们是按照某个顺序先后到达餐厅的，第i个到达餐厅的要求坐在离门口至少a[i]的距离。牛兄牛弟们不准备让别人知道他们是兄弟，虽然他们长得比较像，他们决定任意两个兄弟之间的距离都要大于等于d。餐厅服务员记录下他们的需求之后，开始陆续给到来的牛兄弟们排座位，服务员每次会指定一个满足要求的离门口最近的座位给新到的牛。第一行输入两个整数n,d。第二行输入n个数a[i]。1 ≤ n ≤ 1000, 1 ≤ d,a[i] ≤ 106。输出n个数表示每头牛要做的位置。

测试样例

样例1

输入

4 10
1 21 11 7

输出

1 21 11 31

样例2

输入

4 11
1 21 11 7

输出

1 21 32 43

样例3

输入

4 1000000
1000000 1000000 1000000 1

输出

1000000 2000000 3000000 4000000

解题思路

首先我们要读懂题干，每一个牛都有自己至少要坐的位置，可以大于这个位置，但是不能小于他，同时还要满足和其他的每一个牛兄弟间距至少为d。那么为了保证得到的是最小的位置，我们就有以下两种情况（这里以样例1为例）：

第一头牛就坐在题干给出的位置即可所以坐在位置1，而牛2至少要坐在21，同时检验确实和牛1间距大于10，所以21就是牛2能做的最小位置了。而牛3坐在了牛2的内侧11，我们对其位置进行逐一检验，他和牛1牛2确实间距都为10满足条件，所以牛2坐在11即可。然而牛4坐在7明显与牛3间距小于10，那么无论怎么坐，他都不可能坐在牛3内侧了，所以他要坐在牛3外侧11+10=21，发现和牛2冲突，所以还要继续向外走一个d,所以坐在21+10=31处。自此我们总结出来一个规律：

第一个牛直接坐下就行
其他的牛如果能够坐在内侧，那么就坐在内侧
如果不能坐在内侧，那么就只能不断的向外移，移动距离为d
如果坐在外侧仍然不满足条件，那么继续向外移

解题代码

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

int main()
{
    int n, d;
    //存入牛数量，和最小距离
    cin >> n >> d;
    int arr[10000] = {}; //题干的最小距离
    int ans[10000] = {}; //答案数组
    for (int i = 1; i <= n; i++)
    {
        cin >> arr[i];
    }
    //第一个牛就做到题干给出的位置即可
    ans[1] = arr[1];
    for (int i = 2; i <= n; i++)
    {
        //其他的牛先做到题干给出位置
        ans[i] = arr[i];
        //排序
        sort(arr + 1, arr + i);
        for (int j = 1; j < i; j++)
        {
            //如果第i头牛做的位置在j的内侧且不满足条件，那么就只能做到a[j]+d
            //同理如果坐到外侧不满足条件，也是做到a[j]+d
            if (abs(arr[i] - arr[j]) < d)
            {
                arr[i] = arr[j] + d;
                ans[i] = arr[i];
            }
            else
                //满足条件直接坐下即可
                ans[i] = arr[i];
        }
    }
    for (int i = 1; i <= n; i++)
    {
        cout << ans[i] << " ";
    }
    cout << endl;
    system("pause");
    return 0;
}

NC13222-音乐研究

题目链接

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

题目描述

美团外卖的品牌代言人袋鼠先生最近正在进行音乐研究。他有两段音频，每段音频是一个表示音高的序列。现在袋鼠先生想要在第二段音频中找出与第一段音频最相近的部分。具体地说，就是在第二段音频中找到一个长度和第一段音频相等且是连续的子序列，使得它们的 difference 最小。两段等长音频的 difference 定义为：difference = SUM(a[i] - b[i])2 (1 ≤ i ≤ n),其中SUM()表示求和。其中 n 表示序列长度，a[i], b[i]分别表示两段音频的音高。现在袋鼠先生想要知道，difference的最小值是多少？数据保证第一段音频的长度小于等于第二段音频的长度。

第一行一个整数n(1 ≤ n ≤ 1000)，表示第一段音频的长度。第二行n个整数表示第一段音频的音高（0 ≤ 音高 ≤ 1000）。第三行一个整数m(1 ≤ n ≤ m ≤ 1000)，表示第二段音频的长度。第四行m个整数表示第二段音频的音高（0 ≤ 音高 ≤ 1000）。

测试样例

输入

输出

解题思路

大水题，直接暴力枚举检验即可。细节是注意开始点和结束点位置。

解题代码

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

const int N = 1005;
int a[N], b[N];

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    int m;
    cin >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> b[i];
    }
    int ans = 1e9;
    for (int i = 1; i <= m - n + 1; i++)
    {
        int sum = 0;
        for (int j = i; j <= i + n - 1; j++)
        {
            sum += (a[j - i + 1] - b[j]) * (a[j - i + 1] - b[j]);
        }
        ans = min(ans, sum);
    }
    cout << ans << endl;
    system("pause");
    return 0;
}