[NERC2018] Guest Student

Genshineer · 2023-10-28 21:20:13 · 题解

考虑将中间经过的时间分成三段：若干个整星期，前面的散块，后面的散块。

可以先考虑没有前面的散块的做法：

• 设经过了 res 个整星期，记每个整星期有 cnt 天有空，显然中间每次有空都选择听课是最优的，可以发现 res=7\times\lfloor\dfrac{k-1}{cnt}\rfloor，此时剩下需要安排的课程数为 k-\lfloor\dfrac{res}{7}\rfloor\times cnt。由于剩下的天数不超过 7，所以可以直接扫过整个星期并累加答案。

int get(int x) {
    int res = 7 * ((x - 1) / cnt);
    x -= (res / 7) * cnt;
    for (int i = 1; i <= 7 and x; i++) {
        res++;
        x -= a[i];
    }
    return res;
}

接下来可以发现，前面的散块只有 6 种情况，即以一个星期的每天作为开头的散块，不妨考虑直接“旋转” a 数组，从星期一开头开始枚举，每次统计完答案直接把开头的元素扔到数组尾部。可以证明，这一做法与直接处理前面的散块是等价的，从而极大地降低了程序地实现难度。

#include <bits/stdc++.h>
#define int long long
using namespace std;

int TestCase, k, a[10], ans, cnt;

void rtt() { // Rotate
    int tmp = a[1];
    for (int i = 1; i < 7; i++) a[i] = a[i + 1];
    a[7] = tmp;
}

int get(int x) {
    int res = 7 * ((x - 1) / cnt);
    x -= (res / 7) * cnt;
    for (int i = 1; i <= 7 and x; i++) {
        res++;
        x -= a[i];
    }
    return res;
}

signed main() {
//Fast IO
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    cin >> TestCase;
    while (TestCase--) {
        cin >> k;
        cnt = 0, ans = 1e18;
        for (int i = 1; i <= 7; i++) cin >> a[i], cnt += a[i];
        for (int i = 1; i <= 7; i++) {
            ans = min(ans, get(k));
            rtt();
        }
        cout << ans - 1<< "\n";
    }
}

另给出官方题解供参考：

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); i++)

const int N = 7;

int main() {
    int testCaseCount;
    cin >> testCaseCount;
    forn(testCase, testCaseCount) {
        int k;
        cin >> k;
        vector<int> a(N);
        forn(i, N)
            cin >> a[i];
        int sum = accumulate(a.begin(), a.end(), 0);
        int result = INT_MAX;
        forn(i, N)
            if (a[i] == 1) {
                int n = max(0, k / sum - 1);
                int j = i, cur = n * sum, m = n * 7;
                while (cur < k) {
                    cur += a[j];
                    j = (j + 1) % N;
                    m++;
                }
                result = min(result, m);
            }
        cout << result << endl;
    }
}