题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=6651

题目:


n个问题,每个问题的分数都是整数,范围在【0,m】,若某个问题的分数是x, 那么要花x+1个小时准备才能解决这个问题。

问:若至少要解决k个问题,最少需要准备多少个小时?

 

解题思路:


如果不能解决k个问题,最好的情况是能解决k-1个问题,剩下n-k+1个问题是无法解决的,最惨的情况是这n-k+1个问题每个问题的分数和准备的时间相同。因为在准备的时候不知道每个题目对应的分数,那么为了能够把k-1个问题都解出来,每个问题的准备时间都是(毕竟能解出k-1道,这时可以想成k-1道是白给你的,题目占分没啥意义)。若想解出k个问题,必须在剩下的n-k+1个问题中保证能解出来一个问题,那么准备的时间最小为m+1。

最终答案:

 

ac代码:


#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    ll t, n, m, k;
    scanf("%lld", &t);
    while(t--)
    {
        scanf("%lld %lld %lld", &n, &m, &k);
        ll ans = (m / (n - k + 1) + 1) * (k - 1) + m + 1;
        printf("%lld\n", ans);
    }
    return 0;
}