ABC318

V_Melville精進録 / 2023-09-03 / 原文

T1：Full Moon

模拟

代码实现

n, m, p = map(int, input().split())
ans = 0
i = m 
while i <= n:
    ans += 1
    i += p
print(ans)

或者答案是 \(\lfloor\frac{n+(p-m)}{p}\rfloor\)

T2：Overlapping sheets

模拟

代码实现

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

int main() {
    int n;
    cin >> n;
    
    int m = 100;
    vector s(m, vector<int>(m));
    rep(_, n) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        for (int i = a; i < b; ++i) {
            for (int j = c; j < d; ++j) {
                s[i][j] = 1;
            }
        }
    }
    
    int ans = 0;
    rep(i, m)rep(j, m) if (s[i][j] == 1) ans++;
    
    cout << ans << '\n';
    
    return 0;
}

T3：Blue Spring

贪心

先将 \(f\) 做升序排序
预处理一下 \(f\) 的前缀和
可以枚举后缀哪几个 \(d\) 天买一日游券，剩下的前缀就都是买常规票

代码实现

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;

int main() {
    int n, d, p;
    cin >> n >> d >> p;
    
    vector<int> f(n);
    rep(i, n) cin >> f[i];
    
    sort(f.begin(), f.end());
    
    ll now = 0;
    rep(i, n) now += f[i];
    ll ans = now;
    while (f.size()) {
        ll s = 0;
        int sz = min<int>(d, f.size());
        rep(i, sz) {
            s += f.back();
            f.pop_back();
        }
        now -= s; now += p;
        ans = min(ans, now);
    }
    
    cout << ans << '\n';
    
    return 0;
}