题意:
现在有一场考试,涉及n道题,总共m分。你不知道每门学科的所占分值(0-m),如果复习一门分值为x的学科,需要x+1小时。问你如果至少要答对k道题需要至少复习多久。无论他怎么分配分值。
题解:
很有意思的一道题目,从一脸懵逼到有点懵逼再到wa,搞了半天才A。
它就是考你对极端情况的理解吧。这个也不好说,虽然代码只有几行,但是要分析半天。
首先我们要取学k个问题,那么极端情况是不是有k-1是0分的?也就是说你有k-1白复习了,这样它再将m分配到n-k+1中,这样是极端情况。为什么?
假设它有k个是0,那么你成功的范围是不是就是每个问题1~m+1
如果它有小于k是0,假设有x(x<k),那么是不是将m分配到n-x+1个位置上啊,那么平均值就降低了,也就是说k个的时候是最极端的情况。
但是这时候会有多种情况:我有a个问题不学了,留下n-a重复刚才的过程。这个我乍一看以为是一个双勾函数,直到我打了个表。才发现应该是a=0的时候最优。
那么接着刚才的思路。我们n-k+1个问题中怎么分配使得最大值最小?并不是直接取m/(n-k+1),对于这n-k+1来说,最劣分配是n-k+1-(m%(n-k+1))个问题是m/(n-k+1)+1,剩下的是m/(n-k),那么我们只需要有n-k+1-(m%(n-k+1))+1个问题是m/(n-k+1),剩下的是m-1即可。注意我们本意是在这n-k+1中取到一个即可,所有只需要比m/(n-k+1)+1的个数多1个,剩下的是m/(n-k+1)-1,就至少能取到1个m/(n-k+1)。
也就是减去1*(n-k+1-m%(n-k+1)-1),也就是m/(n-k+1)-1的数量
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,k;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%lld%lld%lld",&n,&m,&k);
printf("%lld\n",(m/(n-k+1)+1)*n-(n-k+1-m%(n-k+1)-1));
}
return 0;
}