BUPT 2021 Winter Training #12

链接:https://vjudge.net/contest/481673#overview

A - Natives

水题略

D - Exam registration

题意

n天之中,每天有\(a_i\)人考试,当天考试人数上限为\(b_i\)人。当前情况可能不合法,即存在\(a_i\geq b_i\).调整考生的考试时间来让整个考试安排合法,并且使得考试天数变动最大的学生变动最小。

思路

二分答案。确定最大调整天数后,先把每天的考试人数清空,即每天的考试人数都为0,再从左到右往里放每天的考试人员,贪心地尽量往左堆叠(不能超过范围)。如果某一步存在范围之内无法堆叠地情况该二分值就不合法。

代码
#include <bits/stdc++.h>
typedef long long ll;
ll a[1000010], b[1000010], t[1000010];
int n;
bool check(int k)
{
    for (int i = 1; i <= n; i++) a[i] = 0;
    int j = 1;
    for (int i = 1; i <= n; i++)
    {
        ll tt = t[i];
        while (tt)
        {
            while (j <= n && ((j <= i + k && a[j] == b[j]) || j < i - k)) j++;
            if (j == i + k + 1 || j == n + 1) return false;
            ll move = std::min(tt, b[j] - a[j]);
            a[j] += move;
            tt -= move;
        }
    }
    return true;
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lld", &t[i]);
    for (int i = 1; i <= n; i++) scanf("%lld", &b[i]);
    int l = 0, r = n + 1;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    if (l == n + 1)
        printf("-1\n");
    else
        printf("%d\n", l);
    return 0;
}

F - Counting Antibodies

水题略

上一篇:12.Innodb数据页的结构01


下一篇:{金言}2015.11-12