题解 | #牛兄牛弟#

知识点:

枚举

思路:

按顺序来为每一个牛i安排位置
然后j用来表示他的位置
	检查以入座的牛p和j有没有abs(p-j)<d
    	如果有p说明j不能用了,并记录最小的p和最大的p

我的这个思路不太好，但是对于我来说很直观。

我观看了https://ac.nowcoder.com/acm/problem/blogs/21781 的题解，发现他的方法好像更快。

他的思考是每一次安排位置后,排序(不包含最新加入的),这样只要去看旧的里面有没有不符合的位置(他的哪个判断可以改成abs(p-j)<d)

我的代码:

#include<iostream>
#include<algorithm>
#include<vector>
#include<math.h>
#include<cfloat>
#include<set>
#include<unordered_map>
using namespace std;


void solve() {
    int n, d,index=0;
    cin >> n >> d;
    vector<int> a(n);
    vector<int> pos;
    for (int i = 0;i < n;i++)    cin>>a[i];

    //按照顺序安排位置
    for (int i = 0; i < n; i++)
    {
        //安排第i只牛,j是他的位置
        int j = a[i];
        while (1) {
            bool ok = true;
            int newpos = j,newpos1=j;
            // check
            for (int p : pos) 
                if (abs(p - j) < d) ok = false,newpos = max(newpos, p),newpos1 = min(newpos1, p);
            
            // 成功安排
            if (ok) {
                pos.push_back(j);
                break;
            }
            // 未成功，优先按照最大的位置进行更新
            if (newpos > j)
                j = newpos + d;
            else j = newpos1 + d ;
        }
    }

    for (int j : pos)  cout << j << " ";

}


int main() {
    std::ios::sync_with_stdio(false); std::cin.tie(0);
    solve();
    return 0;
}