把空房间分配到环上的间隔里，最少相邻住人边数为 max(0, 2n-m)。
OJ: luogu
题目 ID: P9585
难度:普及-
标签:数学构造
日期: 2026-06-18 20:59
题意
在一个有 m 个房间的环上安排 n 位客人，每个房间最多住 1 人。
每位客人的愤怒值等于左右相邻房间里住人的数量，要求最小化所有客人的总愤怒值。
思路
先看一个可以直接验证想法的朴素解：
小数据时可以枚举哪些房间住人，直接统计总愤怒值。
cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
int best = INT_MAX;
for (int mask = 0; mask < (1 << m); mask++) {
if (__builtin_popcount((unsigned) mask) != n) continue;
int anger = 0;
for (int i = 0; i < m; i++) {
if (((mask >> i) & 1) == 0) continue;
int left = (i - 1 + m) % m;
int right = (i + 1) % m;
anger += (mask >> left) & 1;
anger += (mask >> right) & 1;
}
best = min(best, anger);
}
cout << best << '\n';
return 0;
}下面是另一种「01 序列」风格的暴力写法。它按房间编号依次决定住人或空着，递归生成完整选择后，叶子节点统一检查是否正好住 n 个人，并统计怒气值：
另一种暴力写法：01 序列
cpp
// brute_01_style.cpp：01 序列风格暴力，按房间编号依次决定住人或空着。
#include <bits/stdc++.h>
using namespace std;
const int MAXM = 25;
int n, m;
int occupied[MAXM]; // occupied[i] 表示第 i 个房间是否住人。
int best;
int calc_anger() {
int anger = 0;
for (int i = 0; i < m; i++) {
if (!occupied[i]) {
continue;
}
int left = (i - 1 + m) % m;
int right = (i + 1) % m;
anger += occupied[left];
anger += occupied[right];
}
return anger;
}
bool check() {
int cnt = 0;
for (int i = 0; i < m; i++) {
if (occupied[i] == 1) cnt++;
}
return cnt == n;
}
void dfs_room(int pos) {
if (pos == m) {
if (check()) {
best = min(best, calc_anger());
}
return;
}
// 第 pos 个房间的 01 选择：0 空着，1 住人。
for (int i = 0; i <= 1; i++) {
occupied[pos] = i;
dfs_room(pos + 1);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
best = 1000000000;
dfs_room(0);
cout << best << '\n';
return 0;
}关键在于把问题看成“空房间分配到环上的间隔里”。
n 位客人围成一圈后，中间有 n 个间隔。
总共有 m - n 个空房间可以放进这些间隔里。
每当某个间隔至少放 1 个空房间，就能切断 1 条相邻住人边。
因此最少的相邻住人边数就是：
text
max(0, 2n - m)而每条相邻住人边会给答案贡献 2，所以总愤怒值最小为：
text
2 * max(0, 2n - m)代码
cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
int adjacent_pairs = max(0, 2 * n - m);
cout << 2 * adjacent_pairs << '\n';
return 0;
}复杂度
主解只做常数次计算，时间复杂度
总结
这题的关键是把环上住人问题转成“间隔里能放多少空房间”的计数。