秋季笔试算法-电容充电
牛客网《2019年笔试真题精选》 2018年秋季字节跳动笔试题4
主题描述有一个由电容组成的计算器，每个电容组件都有最大容量值（正整数）。 对于单个电容器，操作说明如下： 指令1:放电操作-清除电容器当前电量值 指令2:充电操作-将当前电容补充到最大容量值 两个电容A和B，操作说明如下： 指令3:转移操作-从A中尽可能多地转移电量B，转移不会有电量损失。如果能充满B的最大容量，剩余电量仍将留在A中
现在已知有两个电容，最大容量是a和b其初始状态为0，希望通过一系列操作，使其中一个电容器无论哪一个)中的电量值等于0c（c也是正整数)，这一系列操作中使用的正整数)M，无论如何操作，都不可能完成，此时定义M=0。 显然，每组都确定了a、b、c，会有一个M对应。
每组试样的输入格式为： 第一行是正整数N 从第二行开始，每行由三个正整数组成a、b、c，一共有N组 输出为N行，每行打印每组对应M 数据范围： N： 0 < N < 100 0 < N < 100 0<N<100 a、b、c： 0 < a 、 b 、 c < 1 0 5 （ 50 % ） 0 < a、b、c < 10^5（50\%） 0<a、b、c<105（50%） 0 < a 、 b 、 c < 1 0 7 （ 30 % ） 0 < a、b、c < 10^7（30\%） 0<a、b、c<107（30%） 0 < a 、 b 、 c < 1 0 9 （ 20 % ） 0 < a、b、c < 10^9（20\%） 0<a、b、c<109（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。
若 c > a c > a c>a且 c > b c > b c>b，则显然不可能完成，M为0。 若 c = a c = a c=a或 c = b c = b c=b，则显然一次操作可完成，M为1。 现在考虑剩余情况，即 c < M a x ( a , b ) c < Max(a, b) c<Max(a,b)且 c ≠ M i n ( a , b ) c \neq Min(a, b) c̸=Min(a,b)（条件1）
这里我们将电容A、B看作一个整体，整体电容只有充电和放电两种操作。其中充电使整体总电量增加，放电使整体总电量减少。 则系统总电量可以达到的数值为 a x + b y ax + by ax+by（x、y为整数），其中 x x x、 y y y中为正的表示充电，为负的表示放电。因为条件1，所以 x x x、 y y y一定是一正一负，即 x y < 0 xy < 0 xy<0。 要使电量为c，则要满足等式 a x + b y = c ax + by = c ax+by=c。根据 裴蜀定理 ，等式可以满足当且仅当 g c d ( a , b ) ∣ c gcd(a,b)|c gcd(a,b)∣c，即a，b的最大公约数也是c的因子。 相反，若 c m o d    g c d ( a , b ) ≠ 0 c \mod gcd(a, b) \neq 0 cmodgcd(a,b)̸=0，则电量不能达到c，M为0。
现在假设 g c d ( a , b ) ∣ c gcd(a,b)|c gcd(a,b)∣c，即存在一正一负的整数 x x x， y y y满足等式 a x + b y = c ax + by = c ax+by=c，，则整体电容的具体操作流程如下：
- 给电容A充电
- 电容A转移到电容B
- 若电容B满电，则其放空电量
- 如果电容A电量非空，则转2
- 转1重复执行整个过程，直到某时刻电容A或B中电量为c为止
其电容操作次数有如下两种情况： （1）若 c > a c > a c>a（此时 a < c < b a < c < b a<c<b），则最终是B中先有c的电量（A存不下），此时有 x x x次充电， − y -y −y次放电， x − y x-y x−y次转移（因为B中先有c的电量，每次A充电必然要转移到B，每次B放电必然A非空由步骤4转步骤2进行转移操作），共 2 ( x − y ) 2(x-y) 2(x−y)次操作。 （2）若 c < a c < a c<a（此时 c < a 且 c < b c < a 且 c < b c<a且c<b），则最终是A中先有c的电量（若B中先有，因为 a 、 b a、b a、b都大于 c c c，所以必然是A转移c电量给空的B，此时A先有c电量，矛盾），此时有 x x x次充电， − y − 1 -y - 1 −y−1次放电（当A中有c的电量时，必然是转移给B后，A中剩余c的电量，此时B中满电量不用放电也满足题目要求，所以公式计算的放电次数需要减1）， x − y − 1 x - y - 1 x−y−1次转移（即实际需要充电次数 x x x加上实际需要放电次数 − y − 1 -y - 1 −y−1），共 2 ( x − y − 1 ) 2(x - y - 1) 2(x−y−1)次操作。
因此只需要最小化 ∣ x ∣ + ∣ y ∣ |x| + |y| ∣x∣+∣y∣。若使用扩展欧几里德算法求出任意一组解 ( x , y ) (x, y) (x,y)，则等式 a x + b y = c ax + by = c ax+by=c的全部整数解为： { x + k b / g c d ( a , b ) y − k a / g c d ( a , b ) , k = . . . , − 2 , − 1 , 0 , 1 , 2 , . . . \left\{\begin{matrix} x + kb / gcd(a, b) \\ y - ka / gcd(a, b) \end{matrix} , k = ..., -2, -1, 0, 1, 2, ... \right. { x+kb/gcd(a,b)y−ka/gcd(a,b),k=...,−2,−1,0,1,2,... 找出其中距离 0 0 0最近的两组解 ( x , y ) (x, y) (x,y)（一组 x > 0 x > 0 x>0，另一组 y > 0 y > 0 y>0），其中 ∣ x ∣ + ∣ y ∣ |x| + |y| ∣x∣+∣y∣ 最小的一组就是达到最小操作数的解 ( x , y ) (x, y) (x,y)，根据上面分析可得到最小操作数。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL extend_gcd(LL a, LL b, LL &x, LL &y) // 扩展欧几里德算法
{
if(0 == b)
{
x = 1;
y = 0;
return a;
}
LL q = extend_gcd(b, a % b, x, y);
int t = x;
x = y;
y = t - a / b * y;
return q;
}
int main()
{
int N;
cin >> N;
while(N --) {
LL a, b, c, x, y;
cin >> a >> b >> c;
int d = extend_gcd(a, b, x, y); // ax + by = d
if(c > a && c > b || c % d) {
// 不可能完成
cout << 0 << endl;
continue;
}
if(c == a || c == b) {
// 1次操作完成
cout << 1 << endl;
continue;
}
if(y > 0) {
// xy < 0，令x > 0（x < 0时将a、b，x、y交换）
swap(x, y);
swap(a, b);
}
// 使ax + by = c （d是c的因子，即对上面式子ax + by = d两边同时乘以c / d）
x *= c / d;
y *= c / d;
LL a2 = a / d, b2 = b / d;
LL k = x / b2;
x -= k * b2; // 使这组(x, y)最接近0（x > 0时的整数解）
y += k * a2;
LL res;
if(c > a) // 情况(1)
res = 2 * (x - y);
else // 情况(2)
res = 2 * (x - y - 1);
x -= b2; // 使这组(x, y)最接近0（y > 0时的整数解）
y += a2;
if(c > b) // 情况(1)
res = min(res, 2 * (y - x)); // 上文分析中假设x > 0，这里y > 0
else // 情况(2)
res = min(res, 2 * (y - x - 1));
cout << res << endl;
}
}
参考：
- https://www.acwing.com/blog/content/17/
- https://baike.baidu.com/item/裴蜀定理
- https://baike.baidu.com/item/扩展欧几里德算法