hdu 4611 Balls Rearrangement(数学：推理+模拟)

本文主要是介绍hdu 4611 Balls Rearrangement(数学：推理+模拟)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一道很蛋疼的题

列出几组数据会发现是有规律的

一个数字可能会连续出现多次

虽然发现了规律，但是不知道该怎么写

看了大牛的博客。。。也是醉了

因为一个最小公倍数周期内结果是固定的，所以如果n>lcm，可以优化处理

这道题比较奇葩的地方是用scanf就wa，用cin就过了

代码如下：

#include <cstdio>
#include <iostream>
#include <algorithm>
#define MAXN 10010
#define LL long long
using namespace std;LL gcd(LL a, LL b) {return b ? gcd(b, a%b) : a;
}LL Cost(LL n, LL a, LL b) {//now代表当前的数//x, y代表当前now对a b的模//tmp代表当前的差值LL now, ret, tmp, x, y;now = ret = x = y = tmp = 0ll;while(now < n) {tmp = min(a-x, b-y);if(now+tmp > n)tmp = n-now;ret += tmp*abs(x-y);now += tmp;x = now%a;y = now%b;}return ret;
}int main(void) {int T;LL ans, n, a, b;scanf("%d", &T);while(T--) {cin >> n >> a >> b;LL lcm = a/gcd(a,b)*b;if(lcm >= n)ans = Cost(n, a, b);else ans = Cost(lcm, a, b)*(n/lcm)+Cost(n%lcm, a, b);cout << ans << endl;}return 0;
}

这篇关于hdu 4611 Balls Rearrangement(数学：推理+模拟)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---