codeforces 1706 D1 D2

阅读量: searchstar 2022-07-24 16:27:35
Categories： Tags：

D1 (O(nanlog(n)))

链接：https://codeforces.com/contest/1706/problem/D1

滑动窗口，每个pi从1开始逐渐递增，维护窗口内的最大的和最小的。每次滑动复杂度O(log(n))，每个ai有an个pi需要遍历，所以复杂度O(nanlog(n))。

代码：

#include <cstdio>
#include <queue>

using namespace std;

constexpr int MAXN = 3011;

int main() {
	int T;
	static int a[MAXN];
	static int p[MAXN];

	scanf("%d", &T);
	while (T--) {
		int n, k;
		scanf("%d%d", &n, &k);
		for (int i = 1; i <= n; ++i) {
			scanf("%d", a + i);
		}
		int ans = 0x3f3f3f3f;
		int mn = 0x3f3f3f3f;
		priority_queue<pair<int, int> > pq;
		for (int i = 1; i <= n; ++i) {
			p[i] = 1;
		}
		for (int i = 1; i <= n; ++i) {
			pq.push(make_pair(a[i], i));
			mn = min(mn, a[i]);
		}
		while (1) {
			int mx = pq.top().first;
			int i = pq.top().second;
			pq.pop();
			ans = min(ans, mx - mn);
			if (p[i] == k) {
				break;
			}
			p[i] += 1;
			int v = a[i] / p[i];
			pq.push(make_pair(v, i));
			mn = min(mn, v);
		}
		printf("%d\n", ans);
	}

	return 0;
}

D1 ()

注意到只有个可能取值，因此可以用数论分块遍历这个可以让取不同值的pi。复杂度降为。

代码：

#include <cstdio>
#include <queue>

using namespace std;

constexpr int MAXN = 3011;

int main() {
	int T;
	static int a[MAXN];
	static int p[MAXN];

	scanf("%d", &T);
	while (T--) {
		int n, k;
		scanf("%d%d", &n, &k);
		for (int i = 1; i <= n; ++i) {
			scanf("%d", a + i);
		}
		int ans = 0x3f3f3f3f;
		int mn = 0x3f3f3f3f;
		priority_queue<pair<int, int> > pq;
		for (int i = 1; i <= n; ++i) {
			p[i] = 1;
		}
		for (int i = 1; i <= n; ++i) {
			pq.push(make_pair(a[i], i));
			mn = min(mn, a[i]);
		}
		while (!pq.empty()) {
			int mx = pq.top().first;
			int i = pq.top().second;
			pq.pop();
			ans = min(ans, mx - mn);
			if (mx == 0)
				break;
			p[i] = a[i] / mx + 1;
			if (p[i] > k)
				break;
			int v = a[i] / p[i];
			pq.push(make_pair(v, i));
			mn = min(mn, v);
		}
		printf("%d\n", ans);
	}

	return 0;
}

D2 ()

D2的n和an的范围都变成了1e5。考虑如何将维护窗口内的最大的的复杂度降至O(1)。

注意到值域仅为1e5，因此可以采用类似桶排序的思路，搞一个数组v，vx表示满足的i构成的集合。然后从大到小遍历这个数组，当前遍历到的下标就是当前窗口的的最大值。

代码：

#include <cstdio>
#include <vector>

using namespace std;

constexpr int MAXN = 100011;
constexpr int MAXV = 100011;

int main() {
	int T;
	static int a[MAXN];
	static int p[MAXN];

	scanf("%d", &T);
	while (T--) {
		int n, k;
		scanf("%d%d", &n, &k);
		for (int i = 1; i <= n; ++i) {
			scanf("%d", a + i);
		}
		int ans = 0x3f3f3f3f;
		int mn = 0x3f3f3f3f;
		vector<int> v[MAXV];
		for (int i = 1; i <= n; ++i) {
			p[i] = 1;
		}
		int mx = a[1];
		for (int i = 1; i <= n; ++i) {
			v[a[i]].push_back(i);
			mn = min(mn, a[i]);
			mx = max(mx, a[i]);
		}
		for (; mx; mx -= 1) {
			if (v[mx].empty())
				continue;
			for (int i : v[mx]) {
				ans = min(ans, mx - mn);
				p[i] = a[i] / mx + 1;
				if (p[i] > k)
					goto out;
				int val = a[i] / p[i];
				v[val].push_back(i);
				mn = min(mn, val);
			}
			v[mx] = vector<int>();
		}
out:
		printf("%d\n", ans);
	}

	return 0;
}

D2 (O(anlog(an)))

假设已知，那么我们就要最大化（但不大于v）每个。对于每个给定的ai，我们其实可以算出pi：

要最大化，显然pi越小越好，所以pi应该取。

换句话说，假如pi的取值应该为u，那么这个ai应该满足：

这里官方题解ai的右边界是闭合的：https://codeforces.com/blog/entry/105008。我觉得不对，不然边界上的u就有两种取值了。

这样，我们遍历u = 1, 2, ..., k，把[(u−1)(v+1), u(v+1))范围内的ai的pi全部设为u，即可最大化的最小值。

但是怎么求出这个最小值呢？注意到对每个u，的最小值是用[(u−1)(v+1), u(v+1))范围内最小的ai取到的，因此维护区间最小值即可。注意到[(u−1)(v+1), u(v+1))范围内的区间最小值（如果有的话）和[(u−1)(v+1),  + ∞)范围内的区间最小值相同，因此可以直接预计算出后缀最大值。遍历u的时候，查看[(u−1)(v+1),  + ∞)范围内的区间最小值，如果其小于u(v+1)，那么它就是要求的区间最小值，算出对应的，更新全局最小值。

总的算法流程是枚举最大值v，然后枚举u，通过找出对应区间最小的ai算出的最小值，进而找到全局最小值，从而算出对当前v的值的答案。

注意到v到底是不是真的全局最大值其实对答案没有影响，因为如果v其实不是全局最大值，那么算出来的答案是偏大的。因此直接遍历v的值即可。

由于u最大为k，而遍历u时，所有的ai都应该在这里面的某个区间中。所有u的区间并为[0, k(v+1))，因此应该满足an < k(v+1)，即。因此遍历v的值时，应该是从遍历到an。

遍历u时，当时，所有ai都已经被区间包含了，这时就可以得到全局最小的了。因此遍历u时应该从1到。

因此总的复杂度为

代码：

#include <cstdio>
#include <vector>

using namespace std;

constexpr int MAXN = 100011;
constexpr int MAXV = 100011;

int main() {
	int T;
	static int a[MAXN];
	static int ge[MAXV];

	scanf("%d", &T);
	while (T--) {
		int n, k;
		scanf("%d%d", &n, &k);
		a[0] = 0;
		for (int i = 1; i <= n; ++i) {
			scanf("%d", a + i);
		}
		for (int i = n; i; --i) {
			for (int j = a[i]; j > a[i-1]; --j) {
				ge[j] = a[i];
			}
		}
		ge[0] = a[1];
		int ans = 0x3f3f3f3f;
		for (int v = a[n] / k; v <= a[n]; ++v) {
			int mn = 0x3f3f3f3f;
			for (int u = 1; u <= a[n] / (v + 1) + 1; ++u) {
				int ai = ge[(u - 1) * (v + 1)];
				if (ai < u * (v + 1)) {
					mn = min(mn, ai / u);
				}
			}
			ans = min(ans, v - mn);
		}
		printf("%d\n", ans);
	}

	return 0;
}
pacman使用笔记
数论分块