题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6651
题意:n个科目,总共m分,通过一科需要复习花费科目分数+1分钟,在不知道科目分数的情况下,问最少需要复习多少分钟使得一定可以通过至少k科。
因为需要通过k科,所以最坏的情况是n-k+1科复习时间不够(即只通过k-1科),所以我们要让复习时间最少的n-k+1科其中任选一科都不拖后腿。我们将m分
平均分配到n-k+1科中,如果分配不均则让一些科多复习一分钟,同时在其余k-1科都要复习比n-k+1科时间更多。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<string> 5 #include<algorithm> 6 #include<queue> 7 using namespace std; 8 typedef long long ll; 9 int main() { 10 int t; 11 scanf("%d", &t); 12 while (t--) { 13 ll n, m, k; 14 cin >> n >> m >> k; 15 ll q = n - k + 1; 16 ll y = m % q; 17 ll num1 = q - y - 1, num2 = n - num1; 18 cout << num2 * (m / q + 1) + num1 * (m / q) << endl; 19 } 20 }