秋季笔试算法-电容充电

牛客网《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$
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号电容）

1. 充电A
2. 转移A->B
3. 充电A
4. 转移A->B
   此时A中当前电量为2，操作完成，所以输出4。
   对于（2，3，4），显然不可能完成，输出0。

解析：
若$c>a$且$c>b$，则显然不可能完成，M为0。
若$c=a$或$c=b$，则显然一次操作可完成，M为1。
现在考虑剩余情况，即$c<Max(a,b)$且$c̸=Min(a,b)$（条件1）

这里我们将电容A、B看作一个整体，整体电容只有充电和放电两种操作。其中充电使整体总电量增加，放电使整体总电量减少。
则系统总电量可以达到的数值为$ax+by$（x、y为整数），其中$x$、$y$中为正的表示充电，为负的表示放电。因为条件1，所以$x$、$y$一定是一正一负，即$xy<0$。
要使电量为c，则要满足等式$ax+by=c$。根据 裴蜀定理 ，等式可以满足当且仅当 $gcd(a,b)|c$，即a，b的最大公约数也是c的因子。
相反，若$c\mathrm{m}\mathrm{o}\mathrm{d}gcd(a,b)̸=0$，则电量不能达到c，M为0。

现在假设$gcd(a,b)|c$，即存在一正一负的整数$x$，$y$满足等式$ax+by=c$，不妨设$x>0$，则整体电容的具体操作流程如下：

1. 给电容A充电
2. 电容A转移到电容B
3. 若电容B满电，则其放空电量
4. 如果电容A电量非空，则转2
5. 转1重复执行整个过程，直到某时刻电容A或B中电量为c为止

其电容操作次数有如下两种情况：
（1）若$c>a$（此时$a<c<b$），则最终是B中先有c的电量（A存不下），此时有$x$次充电，$-y$次放电，$x-y$次转移（因为B中先有c的电量，每次A充电必然要转移到B，每次B放电必然A非空由步骤4转步骤2进行转移操作），共$2(x-y)$次操作。
（2）若$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$的全部整数解为：
$$\{\begin{array}{c}x+kb/gcd(a,b)\\ y-ka/gcd(a,b)\end{array},k=...,-2,-1,0,1,2,...$$
找出其中距离$0$最近的两组解$(x,y)$（一组$x>0$，另一组$y>0$），其中$|x|+|y|$ 最小的一组就是达到最小操作数的解$(x,y)$，根据上面分析可得到最小操作数。

C++代码：

#include 
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;
	}
}

---

参考：

1. https://www.acwing.com/blog/content/17/
2. https://baike.baidu.com/item/裴蜀定理
3. https://baike.baidu.com/item/扩展欧几里德算法