0大衣的旅行 - 蓝桥云课
问题描述
大衣的学校计划为 K 个同学和 1 个老师安排一次旅行。
他们住宿旅馆的房间形如一个 N 行 M 列的矩阵，这里有 N×M 个房间，房间 (i,j) 可以容纳 Ai,j 个人。
定义房间 (i1,j1) 和 (i2,j2) 的距离为 max(∣i1−i2∣,∣j1−j2∣)。
你的任务安排他们的房间，使老师的房间和距离他最远的学生的房间的距离最小，如果旅馆无法容纳下这 K+1 个人输出 -1。
输入格式
第一行输入一个正整数 T 表示测试数据的组数。
接下来 T 组测试数据每组输入：
- 第一行输入三个正整数 N,M,K 分别表示矩阵的大小和同学的数量。
- 接下来 N 行每行输入 M 个整数表示每个房间能容纳的人数。
输出格式
对于每组测试数据，输出一个整数表示老师的房间和距离他最远的学生的房间的最小距离，如果无法容纳下 K+1 个人输出 -1，并换行。
样例输入1
4
1 5 8
2 4 3
0 2 6 3
0 2 6 3
2 2 7
1 6
1 6
4 1
3 2 3
0 2
1 0样例输出1
2
3
3
-1说明
- 样例1：老师住在房间 (1, 2)，两个学生住在房间 (1, 1)，一个学生住在房间 (1, 4)，两个学生住在房间 (1, 5)。距离老师房间最远的学生的房间为 (1, 5)，距离为 3，可以证明没有其他的安排方式能使最小距离小于 3。
- 样例2：老师和 3 个学生可以都住在房间 (1, 3)，因此距离为 0。
- 样例3：旅馆没有足够的人数容量。
思路：
二分枚举答案，check函数就是证明这个枚举的答案是否满足条件，画完二分图即可
代码：
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
typedef long long ll;
ll N, M, K;
ll check(const vector<vector<ll>>& pre,const vector<vector<ll>>& a,ll mid)
{bool possible = false;for (ll i = 1; i <= N ; ++i) {for (ll j = 1 ; j <= M ; ++j) {if (a[i][j] == 0)continue;ll x1 = max(1LL, i - mid);ll x2 = min(N, i + mid);ll y1 = max(1LL, j - mid);ll y2 = min(M, j + mid);ll sum = pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] + pre[x1-1][y1-1];if (sum >= K + 1) {return true;}}}return false;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);ll T;cin >> T;while (T--) {cin >> N >> M >> K;vector<vector<ll>> a(N + 1, vector<ll>(M + 1, 0));vector<vector<ll>> pre(N + 1, vector<ll>(M + 1, 0));ll total = 0;for (ll i = 1; i <= N; ++i) {for (ll j = 1; j <= M; ++j) {cin >> a[i][j];total += a[i][j];pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j];}}if (total < K + 1) {cout << -1 << '\n';continue;}ll l = 0, r = max(N-1, M-1);ll ans = -1;while (l + 1 != r) {ll mid = (l + r) / 2;if (check(pre,a,mid)) {ans = mid;r = mid;} else {l = mid;}}cout << ans << '\n';}return 0;
}
)
