CF732D Exams

这题可以用二分答案来做

那么为什么可以用二分答案呢？

答案当然是满足了单调性。 假设用$x$天能够考完所有试，那么用大于$x $天必定也能够考完所有试，所以满足了单调性，我们就可以二分答案

那么如何$check$呢？考虑一下贪心

贪心思路：在二分的$mid$天之前找到每一科考试可以考的最后一天，只在这一天去考这一门科目，其它时间积攒复习时间，若在$mid$前这个科目可考的最后一天出现了，而此时积攒的复习时间并不足以考过这门科目，则说明用$mid$天不能考完这些科目，否则就让计数器$cnt$的值加一，表示现在已经考了$cnt$门，最后检验一下$cnt$是否等于$m$，若不等于则说明还有科目在$mid$天前没有出现，增大范围，否则缩小范围，让$ans$等于$mid$。

代码如下

#include <cmath>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int A = 1e5 + 11;

const int B = 1e6 + 11;

inline int read() {

	char c = getchar(); int x = 0, f = 1;

	for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;

	for( ; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);

	return x * f;

}

int n, m, all, cnt;

int d[A], w[A], a[A], la[A];

inline bool check(int x) {

	memset(la, 0, sizeof(la));

	for(int i = 1; i <= n; i++) a[i] = d[i];

	for(int i = 1; i <= x; i++) if(a[i]) a[la[a[i]]] = 0, la[a[i]] = i;

	int tl = 0, cnt = 0;

	for(int i = 1; i <= x; i++) {

		if(a[i]) { tl -= w[a[i]]; if(tl < 0) return 0; else cnt++; }

		else tl++;

	}

	return cnt == m;

}

int main() {

	n = read(), m = read();

	if(n < m) return puts("-1"), 0;

	for(int i = 1; i <= n; i++) d[i] = read();

	for(int i = 1; i <= m; i++) w[i] = read(), all += w[i];

	if(all > n) return puts("-1"), 0;

	int l = 0, r = n, ans = -1;

	while(l <= r) {

		int mid = (l + r) >> 1;

		if(check(mid)) ans = mid, r = mid - 1;

		else l = mid + 1;

	}

	return cout << ans << '\n', 0;

}

巴特西

CF732D Exams

最新文章

热门文章