考虑将中间经过的时间分成三段:若干个整星期,前面的散块,后面的散块。
可以先考虑没有前面的散块的做法:
- 设经过了 \(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;
}
}
标签:cnt,P9797,int,res,NERC2018,cin,Student,散块,forn
From: https://www.cnblogs.com/George-Pig-Orz/p/17794690.html