[54] 电容器充电 - 2018 年秋季字节跳跃
1.题目描述
有一台用电容组成的计算器,其中每个电容组件都有一个最大容量值(正整数)。
对于单个电容,有如下操作指令:
指令1:放电操作-把该电容当前电量值清零
指令2:充电操作-把该电容当前电量补充到其最大容量值
对于两个电容A和B,有如下操作指令:
指令3:转移操作-从A中尽可能多的将电量转移到B,转移不会有电量损失,如果能够充满B的最大容量,那剩余的电量仍然会留在A中
现在已知有两个电容,其最大容量分别为a
和b
,其初始状态都是电量值为0,希望通过一系列的操作可以使其中某个电容(无所谓哪一个)中的电量值等于c
(c
也是正整数),这一系列操作所用的最少指令条数记为M
,如果无论如何操作,都不可能完成,则定义此时M=0
。
显然对于每一组确定的a
、b
、c
,一定会有一个M
与其对应。
- 输入描述:
每组测试样本的输入格式为:
第一行是一个正整数N
从第二行开始,每行都是3个正整数依次组成一组a
、b
、c
,一共有N
组 - 输出描述:
输出为N
行,每行打印每一组的对应的M
- 数据范围:
N
:0<N<100
a
、b
、c
:0
<a
、b
、c
<10^5
(50%)0
<a
、b
、c
<10^7
(30%)0
<a
、b
、c
<10^9
(20%) - 输入示例:
2 3 4 2 2 3 4
- 输出示例:
4 0
- 说明:
对于(3,4,2)
,最少只需要4个指令即可完成:
(设最大容量为3的是A号电容,另一个是B号电容)- 充电A转移A->B
- 充电A转移A->B
此时A中当前电量为2
,操作完成,所以输出4
。
对于(2,3,4)
,显然不可能完成,输出0
。
2.题目解析
- 简单情况
- 若
c>a
且c>b
,则显然不可能完成,M
为0
。 - 若
c=a
或c=b
,则显然一次操作可完成,M
为1
。
- 若
- 其他情况
示例条件- A容量
a=3
- B容量
b=4
- 目标电量
c=2
- A容量
一共有两种方式
小容量的先充电,然后转移到大容量
操作 | A电量(a=3) | B电量(b=4) |
---|---|---|
初始状态 | 0 | 0 |
A充电 | 3 | 0 |
A转移到B | 0 | 3 |
A充电 | 3 | 3 |
A转移到B | 2 | 4 |
指令条数M=4
大容量的先充电,然后转移到小容量
操作 | A电量(a=3) | B电量(b=4) |
---|---|---|
初始状态 | 0 | 0 |
B充电 | 0 | 4 |
B转移到A | 3 | 1 |
B放电 | 0 | 1 |
B转移到A | 1 | 0 |
B充电 | 1 | 4 |
B转移到A | 3 | 2 |
指令条数M=6
从小到大一定比从大到小指令少?
现在考虑剩余情况,即c<Max(a,b)
且c≠Min(a,b)
(条件1)
将电容A、B看作一个整体,整体电容只有充电和放电两种操作。其中充电使整体总电量增加,放电使整体总电量减少,则系统总电量可以达到的数值为ax+by
(a
、b
为整数,且ab<0
),其中x
、y
中为正的表示充电,为负的表示放电。因为条件1,所以a
、b
一定是一正一负,即ab<0
。
要使电量为c
,则要满足等式ax+by=c
。根据裴蜀定理,等式可以满足当且仅当gcd(a,b)|c
,即a
,b
的最大公约数也是c
的因子。
裴蜀/贝祖定理
若是整数,且,那么对于任意的整数,都一定是的倍数,特别地,一定存在整数,使成立。
相反,若c mod gcd(a,b)≠0
,则电量不能达到c
,M
为0
。
现在假设gcd(a,b)|c
,即存在一正一负的整数x
,y
满足等式ax+by=c
,不妨设x>0
,则整体电容的具体操作流程如下:
- 给电容A充电
- 电容A转移到电容B
- 若电容B满电,则其放空电量
- 如果电容A电量非空,则转2
- 转1重复执行整个过程,直到某时刻电容A或B中电量为
c
为止
先给容量大的充电(),还是先给容量小的充电()?
指令条数M
= 转移次数 + 充电次数 + 放电次数
转移次数 = 充电次数 + 放电次数?
其电容操作次数有如下两种情况: 假设(b>a
)
- 若
c>a
(此时a<c<b
),则最终是B中先有c
的电量(A存不下),此时有x
次充电,−y
次放电,x−y
次转移(因为B中先有c
的电量,每次A充电必然要转移到B,每次B放电必然A非空由步骤4转步骤2进行转移操作),共2(x−y)
次操作。 - 若
c<a
(此时c<a
且c<b
),则最终是A中先有c
的电量(反证法:若B中先有,因为a
、b
都大于c
,所以必然是A转移c
电量给空的B,此时A先有c
电量,矛盾),此时有x
次充电,−y−1
次放电(当A中有c
的电量时,必然是转移给B后,A中剩余c
的电量,此时B中满电量不用放电也满足题目要求,所以公式计算的放电次数需要减1
),x−y−1
次转移(即实际需要充电次数x
加上实际需要放电次数−y−1
),共2(x−y−1)
次操作。
因此只需要最小化|x|+|y|
。若使用扩展欧几里德算法求出任意一组解(x,y)
,则等式ax+by=c
的全部整数解为:
找出其中距离0
最近的两组解(x,y)
(一组x>0
,另一组y>0
),其中|x|+|y|
最小的一组就是达到最小操作数的解(x,y)
,根据上面分析可得到最小操作数。
参见[欧几里得算法]与[扩展欧几里得算法]
3.参考答案
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
// 扩展欧几里得算法
LL egcd(LL a, LL b, LL &x, LL &y) {
if (b == 0) {
x = 1, y = 0;
return a;
}
LL q = egcd(b, a % b, y, x);
y -= a / b * x;
return q;
}
int main() {
int N = 0;
scanf("%d",&N);
while (N--) {
LL a, b, c, x, y;
scanf("%lld%lld%lld", &a,&b,&c);
int d = egcd(a, b, x, y); // 这里是ax+by=d
// c大于A和B的容量,不能完成
// 根据裴蜀/贝祖定理,c不是gcd(a,b)的倍数,不能完成
if (c > a && c > b || c % d) {
printf("0\n");
continue;
}
// 刚好1步充满A或者B
if (c == a || c == b) {
printf("1\n");
continue;
}
// 假设a>0
if (y > 0) swap(x, y), swap(a, b);
// 使ax + by = c (d是c的因子,即对上面式子ax + by = d两边同时乘以c / d)
x *= c / d; // 乘上c的约分
y *= c / d;
LL a2 = a / d; // a约分
LL b2 = b / d; // b约分
LL k = x / b2; // |x|+|y|最小的k?????
x -= k * b2; // 使这组(x, y)最接近0(x > 0时的整数解)
y += k * a2;
LL res;
if (c > a)
res = 2 * (x - y);
else
res = 2 * (x - y - 1);
// |x|+|y|最小????
x -= b2;
y += a2;
if (c > b)
res = min(res, 2 * (y - x));
else
res = min(res, 2 * (y - x - 1));
printf("%d\n",res);
}
return 0;
}
上一篇: 模版:约数
下一篇: 算法基础课程 数学知识(二)