T3: 找零
对于 \(20\) 块，优先找 \(10+5\)，其次是 \(5+5+5\)
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
rep(i, n) {
assert(a[i] == 5 or a[i] == 10 or a[i] == 20);
}
int ans = 0;
int c5 = 0, c10 = 0;
rep(i, n) {
if (a[i] == 5) {
ans++;
c5++;
}
if (a[i] == 10) {
if (c5 >= 1) {
ans++;
c10++;
c5--;
}
}
if (a[i] == 20) {
if (c10 >= 1 and c5 >= 1) {
ans++;
c10--;
c5--;
}
else if (c5 >= 3) {
ans++;
c5 -= 3;
}
}
}
cout << ans << '\n';
return 0;
}
T4: 新年灯会
可以找连续的 \(p\) 个灯笼里亮着的最多的那一段就行了，因为亮着的最多，意味着坏掉的灯笼就是最少的
不妨将坏掉的灯笼标记为 0，亮着的灯笼标记为 1
可以用前缀和来加速查询
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int main() {
int n, m, p;
cin >> n >> m >> p;
vector<int> a(n+1, 1);
a[0] = 0;
rep(i, p) {
int t;
cin >> t;
a[t] = 0;
}
rep(i, n) a[i+1] += a[i];
int ans = 0;
rep(i, n-m+1) {
int now = a[i+m] - a[i];
ans = max(ans, now);
}
cout << m-ans << '\n';
return 0;
}