C++:制作火把

制作火把

时间限制 : 1.000 sec          内存限制 : 128 MB

题目描述:

小红最近在玩一个制作火把的游戏,一开始,小红手里有一根木棍,她希望能够通过这一根木棍通过交易换取制作k个火把。一个火把的制作需要消耗一根木棍和一块煤。

幸运的是,在游戏中有这样一个商人,小红可以每次在这个商人这儿进行下面两种交易中的一种交易:

- 通过1根木棍,换取得到x根木棍(即小红失去1根木棍,但能因此得到x根木棍)
- 通过y根木棍,换取得到1块煤(即小红失去y根木棍,得到1块煤)

小红可以和这个商人进行任意次的交易,现在,她需要知道,她最少需要和这个商人交易多少次才能制作出k个火把。

对于每个数据,一共有t组样例。

输入:

第一行输入一个数字t(1 ≤ t ≤ 2 x 10^4),表示数据的组数。

对于每一组数据,只有一行三个数字x,y,k(2 ≤ x ≤ 10^9,1 ≤ y,k ≤ 10^9),分别表示小红可以通过1根木棍交换得到的木棍数量,通过多少根木棍交换得到1块煤,以及小红一共需要的火把数量。

输出:

对于每一组数据,输出一个数字,表示得到k个火把最少需要的交易次数。

样例输入:

5
2 1 5
42 13 24
12 11 12
1000000000 1000000000 1000000000
2 1000000000 1000000000

样例输出:

14
33
25
2000000003
1000000001999999999

这玩意儿怎么做呢?暴力循环又会超时,对新手大大滴不友好 

如果你去模拟几次就能发现,总次数=获得所需木棍次数+所需煤个数

总是要兑换那么多木棍,总是只要那些煤,那就可以将兑换二者的次数分开算

上代码

完整代码:

#include <bits/stdc++.h>
using namespace std;
long long x, y, k, t, ans=0;
long double j;
int main(){
	cin>>t;
	for(int i=0;i<t;i++){
		cin>>x>>y>>k;
		ans=0;
		j=(k*y+(k-1))/(x-1);//获得所需木棍次数
		ans=ceil(j)+k;//总次数=获得所需木棍次数+所需煤个数
		if(ceil(j*(x-1)<k*y+(k-1)))ans++;//会有向下取整而导致答案不对的情况
		cout<<ans<<endl;
	}
	return 0;
}

又是愉悦水题的一天~ 

上一篇:(二分查找)农夫和奶牛


下一篇:QStyle Group Boxes 样式设计(十五)