Final Exam

Time Limit: 4000/2000 MS (Java/Others)

Memory Limit: 524288/524288 K (Java/Others)

Problem Description

Final Exam is coming! Cuber QQ has now one night to prepare for tomorrow’s exam.

The exam will be a exam of problems sharing altogether m points. Cuber QQ doesn’t know about the exact distribution. Of course, different problems might have different points; in some extreme cases, some problems might worth 0 points, or all m points. Points must be integers; a problem cannot have 0.5 point.

What he knows, is that, these n problems will be about n totally different topics. For example, one could be testing your understanding of Dynamic Programming, another might be about history of China in 19th century. So he has to divide your night to prepare each of these topics separately. Also, if one problem is worth x points in tomorrow’s exam, it takes at least x+1 hours to prepare everything you need for examination. If he spends less than x+1 hours preparing, he shall fail at this problem.

Cuber QQ’s goal, strangely, is not to take as much points as possible, but to solve at least k problems no matter how the examination paper looks like, to get away from his parents’ scoldings. So he wonders how many hours at least he needs to achieve this goal.

Input

The first line of the input is an integer $t$ ($1\leq t \leq 20 000$), denoting the number of test cases.

Each test case are three space-separated integers $n$,$m$,$k$ ($0\leq m \leq 10^9, 1 \leq k \leq n \leq 10^9$).

Output

For each test case, output the number of hours Cuber QQ needs.

Sample Input

1
2
3
2
1 10 1
10 109 10

Sample Output

1
2
11
1100

Hint

1
2
Cuber QQ should solve one problem in sample 1, so he at least prepares 11 hours when the problem one is 10 point. 
Cuber QQ should solve all the ten problems in sample 2, so he at least prepares 110 hours for each problem because there may be one problem is 109 point.

题意：

给你 $n$ 个题，这些题目的总分是 $m$，你不知道分数是如何分配的。假设一个题目的分数是 $x$ ，那么如果你想通过这道题，则至少需要花费 $x + 1$ 的时间去复习，现在问你，能够答对 $k$ 道题的最少复习时间是多少。

题意很绕……，前前后后读题大概花了30分钟。这题麻烦就麻烦在，你是不知道分数的分配的，所以如果不从反面加以考虑是很难处理的。

解法

  • 反面

    我们从反面加以考虑，如果你是出题老师，该如何让答题者过不了关？（假设你知道对方的复习情况，这是一个很重要的前提，因为这就是答题者能够碰到的最坏情况,好好想想为什么），那么，我们贪心的去考虑，先把题目按照答题者的复习时间从短到长排个序, 即 ,如果我们尽量想让答题者回答不了 $k$ 题,则需从左到右安排 $A_i$ 的分数,让其分数等于复习时间,即刚好不能答出(为啥先把复习时间少的题目的分数安排好?这就是贪心的地方!因为总分数是有限的,即 $ m $,先安排分数少的可以剩下更多的分数安排后面的)。

  • 正面

    现在你知道出题老师是怎么卡你的了,那我该怎么复习才一定能够过 $k$ 个题目呢?

    同样按照复习时间把问题排序,, 要保证一定能够答对 $k$ 个的话,只需考虑前 $ n - k + 1 $ 个问题不会被卡(注意,已经按照复习时间长短排好序了,出题人卡你的方案如上),即前 $n - k + 1$ 个问题中至少能够答对一个问题!然而出题人能够用的总的分数就是 $ m $ ,那么只要前 $n - k + 1$ 个问题花费的总复习时间超过 $m$ 就可以了，那我们肯定取 $m + 1$ ，即前 $n - k + 1$ 个问题总复习时间为 $m + 1$ ，这样就可以保证前 $n - k + 1$ 个问题里至少可以对 1 个，而卡后面 $k - 1$ 个是不划算的，上面分析了，而我们要让总复习时间最少，则考虑让 最小（想想为什么），然后后面的 个问题也和 取同样的时长。

    所以最终时间就是

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    ll n, m, k;
    scanf("%lld%lld%lld", &n, &m, &k);
    if (n == k) {  // 全部答对
      printf("%lld\n", k * (m + 1));
    } else {
      ll num = n - k + 1;
      // 前 n - k + 1 个问题分配 m + 1 的复习时间， 其中最长复习时间的最小值
      ll sc = ceil((m + 1) * 1.0 / num);
      // 后面 k - 1 个问题的复习时间也取 sc
      printf("%lld\n", m + 1 + sc * (k - 1));
    }
  }
  return 0;
}

总结

总而言之，巨菜……， 疯狂签到 + 挂机自闭划水，要学的东西还很多，思维上差很多。