HDU 6651 Final Exam

死活过不去，就是菜好吧

考虑任何一种可行的复习方式，都是对任意$n - k + 1$个题目都没有一种出题方法使这些题目全挂，

换句话说，复习时间最小的$n - k + 1$个题都没有一种出题方法使它们全挂即可。

如果这些题目的复习时间的总和$\leq m$，那么总能构造出一种分数分配使这些题目全挂，但是只要复习时间的总和来到$m + 1$，那么就至少有一个题目能过。

为了使剩下题目需要的时间最小，这$m + 1$个小时在这$n - k + 1$个题目里面平均分一分，然后剩下的$k - 1$个题的时间不少于这$n - k + 1$个题的复习时间就行，答案为$(m + 1) + (k - 1) * \left \lceil \frac{m + 1}{n - k + 1} \right \rceil$

又有$ \left \lceil \frac{a}{b} \right \rceil = \left \lfloor \frac{a + b - 1}{b} \right \rfloor$

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
using namespace std;
typedef long long ll;

const ll inf = LLONG_MAX;

int testCase;
ll n, m, k;

template <typename T>
inline void read(T &X) {
    char ch = 0; T op = 1;
    for (X = 0; ch > '9' || ch < '0'; ch = getchar())
        if (ch == '-') op = -1;
    for (; ch >= '0' && ch <= '9'; ch = getchar())
        X = (X * 10) + ch - '0';
    X *= op;
}

int main() {
    #ifndef ONLINE_JUDGE
        freopen("sample.in", "r", stdin);
    #endif

    for (read(testCase); testCase--; ) {
        read(n), read(m), read(k);
        ll ans = (m + 1) + (k - 1) * ((m + 1 + n - k) / (n - k + 1));
        printf("%lld\n", ans);
    }
    return 0;
}

View Code