题目描述

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.

输入描述:

Line 1: Two space-separated integers, N and K
Lines 2..N+1: Line i+1 contains height Hi

输出描述:

Line 1: The number of ways that the cows can sit down at the round table such that two adjacent cows do not differ in height by more than K millimeters.

示例1

输入
4 10
2
16
6
10
输出
2
说明
There are 4 cows, with heights 2, 16, 6, and 10. Two cows whose heights differ by more than 10 do not want to sit next to each other.
Clearly the cows with heights 2 and 16 must be opposite each other, so there are 2 ways to place the cows of height 6 and 10.

解答

题目大意 ： 输入牛的数量和限制高度，输出有多少种坐法（所有牛围成一圈）可以让相邻两头牛的高度不超过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;
}

来源：东野圭吾#