题解 | Cows Of The-牛客假日团队赛5C题

Farmer John is calling his N (1 <= N <= 10) cows to a very important meeting at a round table.
The cows are rather anxious about this meeting since they want to put forth their very best image. To make the table arrangement attractive, they want to ensure that any two cows sitting next to each other to differ in height by no more than K (1 <= K <= 1,000,000) millimeters (cow i has integer height Hi (1 <= Hi <= 1,000,000) millimeters).
Help calculate the number of ways the cows can sit down at the round table such that no two adjacent cows differ in height by more than K millimeters. Two ways are different if there is at least one cow with a different cow to its left in each arrangement.
The answer is guaranteed to fit in a 32-bit signed integer.

题目大意 ： 输入牛的数量和限制高度，输出有多少种坐法（所有牛围成一圈）可以让相邻两头牛的高度不超过K

思路 ： 由于数据比较小，可以全排列所有的情况，然后依次判断即可，注意全排列排的是下标

AC代码 ：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 10 + 5;
 
int p[MAXN], s[MAXN], n, k, ans;
 
int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> p[i];
    sort (p + 1, p + n + 1);   // 先排序
    for (int i = 1; i <= n; i++) s[i] = i;
    do {
        bool flag = 1;
        if (abs (p[s[1]] - p[s[n]]) > k) flag = 0;  // 首尾判断
        else {
            for (int i = 2; i <= n; i++) {
                if (abs (p[s[i]] - p[s[i - 1]]) > k) {
                    flag = 0;
                    break;
                }
            }
        }
        if (flag) ans++;
    }
    while (next_permutation (s + 1, s + n + 1));
    cout << ans / n << endl;   // 每种情况都有n - 1个重复的，所以要除以n
    return 0;
}