Solution

思路：二分答案。
问是哪来的？看看题，最小化最大值嘛！
不会有不会二分答案模板的吧？先上一个：

CPP

int l = 1, r = n, mid, ans;
while (l <= r) {
    mid = (l + r) >> 1;
    if (Check(mid)) {
        ans = mid;
        l = mid + 1; // 或 r = mid - 1
    } else r = mid - 1; // 或 l = mid + 1
}
cout << ans << '\n';

但是，这里我们要的是数组中的值，而非

1

至

n

间任意值，所以我们需要一点修改——

CPP

// num数组记录a数组中出现的数
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) num[++cnt] = a[i][j];
sort(num + 1, num + 1 + cnt);
cnt = unique(num + 1, num + 1 + cnt) - num;
// 进行二分
l = 1, r = cnt;
while (l <= r) {
    mid = (l + r) >> 1;
    if (Check(mid)) {
        ans = mid;
        r = mid - 1;
    } else l = mid + 1;
}
cout << num[ans] << '\n';

OKOK，我们现在要的就是 Check 函数了！
将每一个数列（记为

d

）从大到小排序，则可将题转化为最小化

d[k]

的最大值。
由于从大到小排序后期用 STL 不太方便，所以我们选择从小到大排序，然后最小化

d[m - k + 1]

的最大值。
设在某一方案中，

d[m - k + 1]

的最大值的最小值为

t

。
如果该方案可行，则对于每一个

d

，

d[k]

及其之前的每一个数都应小于

t

。
如果有大于的怎么办？我们有

x

次的交换机会，将别的数列中多余的小于

t

的值换到这个序列来，以多补少。
假如够换，OK；假如不够换，那么退而求其次，看别的方案能不能行。这不就是二分的思想吗？
上 Check 代码：

CPP

bool Check(int pos) {
	int t = num[pos], lt = 0, gt = 0;
    for (int i = 1; i <= n; i++) {
        int p = upper_bound(a[i] + 1, a[i] + 1 + m, t) - a[i]; // 要事先将每条数列排序
        if (k >= p) lt += k - p + 1;
        else gt += p - k - 1;
    }
    if (lt <= gt && lt <= x) return true;
    else return false;
}

那么，完整代码呈现一下：

CPP

#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int N = 2e3 + 5;
int n, m, k, x, a[N][N], l, r, mid, ans, num[N * N], cnt = 0;
bool Check(int pos) {
	int t = num[pos], lt = 0, gt = 0;
    for (int i = 1; i <= n; i++) {
        int p = upper_bound(a[i] + 1, a[i] + 1 + m, t) - a[i];
        if (k >= p) lt += k - p + 1;
        else gt += p - k - 1;
    }
    if (lt <= gt && lt <= x) return true;
    else return false;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) cin >> a[i][j], num[++cnt] = a[i][j];
		sort(a[i] + 1, a[i] + 1 + m);
	}
    sort(num + 1, num + 1 + cnt);
    cnt = unique(num + 1, num + 1 + cnt) - num;
	cin >> k >> x;
    k = m - k + 1;
	// max a[k]
	l = 1, r = cnt;
	while (l <= r) {
		mid = (l + r) >> 1;
		if (Check(mid)) {
			ans = mid;
			r = mid - 1;
		} else l = mid + 1;
	}
	cout << num[ans] << '\n';
	return 0;
}

题解：P8088 『JROI-5』Autumn

文章操作

Solution

相关推荐

评论

题解：P8088 『JROI-5』Autumn