CF732D Exams 题解

题目链接

题目分析：

首先可以发现，如果当前第 \(i\) 天可以完成所有考试，那么第 \(i + 1\) 天一定也可以。因此，答案具有单调性。考虑二分，将原问题转换为判定性问题。

判定是否合法时，我们使用贪心。贪心地想，最后一场考试一定要考，因为这样可以积累更多的时间复习。因此我们可以倒着从后往前判断，让后面的试尽可能被考。

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 100010;
bool exams[N];
int n, m, type[N], day[N];

bool check(int n) {
    memset(exams, false, sizeof exams);
    int sum = 0;
    for (int i = n; i; i -- ) {
        if (type[i] && !exams[type[i]])
            sum += day[type[i]], exams[type[i]] = true;
        else if (sum) sum -- ;
    }
    if (sum) return false;
    for (int i = 1; i <= m; i ++ ) if (!exams[i]) return false;
    return true;
}

int solve(int l, int r) {
    if (l >= r) return l;
    int mid = l + r >> 1;
    return check(mid) ? solve(l, mid) : solve(mid + 1, r);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ )
        scanf("%d", &type[i]);
    for (int i = 1; i <= m; i ++ )
        scanf("%d", &day[i]);
    if (!check(n)) return puts("-1"), 0;
    printf("%d\n", solve(1, n));
    return 0;
}