Codeforces Round #688 (Div. 2) A，B

╰半夏微凉° 2022-12-26 11:16 146阅读 0赞

#### A Cancel the Trains ####

###### [传送门][Link 1] ######

##### 题目大意 #####

有 100 个从下向上的火车道，100 个从左向右的火车道，如图所示  
![车道的图][16eb1d36b964ac83ad4d466ff2e3c63b.png]  
所有的火车的速度都是一样的，火车同时出发，同时到达终点，如果在某一时刻两个车同时行驶到了同一个位置，这两辆车就会相撞，就会发生事故。

最开始的时候告诉你那些车道上会有车，然后你要做的是求出最少要取消多少量车，才能使此次行驶没有交通事故。

##### 思路 #####

显然易得，当从下向上的车和从左向右的车的编号相同时，他们会相撞，其他情况下都会不会发生事故，所以我们只要把编号相同的车给取消掉其中一辆就可以了，所以只要统计有多少编号一样的车即可

##### 代码 #####

// 由于本题数据量较小，所以直接暴力即可，本人当时忘了这回事，写的有些复杂了
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    using namespace std;
    int main()
    { 
    	int T;
    	cin >> T;
    	while (T--)
    	{ 
    		int m, n;
    		cin >> m >> n;
    		int mm[101];
    		int nn[101];
    		for (int i = 0; i < m; i++)
    		{ 
    			cin >> mm[i];
    		}
    		for (int i = 0; i < n; i++)
    		{ 
    			cin >> nn[i];
    		}
    		sort(mm, mm + m);
    		sort(nn, nn + n);
    		int lm = 0;
    		int ln = 0;
    		int sum = 0;
    		while (lm != m && ln != n)
    		{ 
    			if (mm[lm] == nn[ln])
    			{ 
    				sum++;
    				lm++;
    				ln++;
    			}
    			else if (mm[lm] < nn[ln])
    			{ 
    				lm++;
    			}
    			else
    			{ 
    				ln++;
    			}
    		}
    		cout << sum << endl;
    	}
    }

#### B Suffix Operations ####

###### [传送门][Link 2] ######

##### 题目大意 #####

有一个数组，你可以对数组做一种操作，每次操作你可以将数组从某一个位置到数组末尾的所有元素同时+1 或-1，然后你需要通过一些这样的操作使数组最后所有元素都相等，你在一开始操作之前可以任将数组中的一个数替换成任意一个数，你需要计算出使数组元素都相等需要操作的最小步数

##### 思路 #####

对于每次操作，如果我们暴力模拟的话，需要把一段区间里的数全都加一或减一，这样太暴力了，肯定不行，所以我们需要观察，每次操作的时候有什么是不变的

显然，**每次操作的时候，除了范围的边界元素之外，其它的所有元素和它相邻的元素的差都是不变的，而边界元素和它相邻元素的差变了一**。

所以我们无需记录数组中的每一个数，我们只要记录每个元素和它前一个元素的差就可以了。然后**使所有元素都相等**也就是**使元素之间的差都变为零**。所以我们**最后要操作的次数，就是所有元素间差的绝对值**。

所以我们最开始操作前的那个改变任意一个数就要尽可能的减去更多的*元素之间差的绝对值*即*步数*。那么先在问题就转化成了最多可以减掉多少步数。

以 1 4 3 2 4 1 这组数来举例

元素之间的差为-3 1 1 -2 3

如果我们改变的数是第一个数或者随后一个数，那么只能影响一个差值，例如把第一个数 1 改成了 4，这样元素之间的差就变成了 0 1 1 -2 3，总共减掉了 abs(-3)也就是 3 步，如果把最后一个数 1 改成了 4，也同理总共减掉了 abs(3)也就是 3 步

如果我们改变的是中间的某个数，那么会影响这个数和它前一个数的差以及这个数和它后面的数的差一共两个差，如果我们修改的是第三个数 3，无论我们是把 3 改成了 4 还是改成了 2，最后 3 和它两边元素的差的总和都是不变的。

原来：-3 **1 1** \-2 3 总和是 |1| + |1| = 2  
改成 4：-3 **0 2** \-2 3 总和是 |0| + |2| = 2  
改成 2： -3 **2 0** \-2 3 总和是 |2| + |0| = 2

我们再看，如果把第二个数 4 改成了 3，会发生什么

原来：**-3 1** 1 -2 3 总和是|-3| + |1| = 4  
改成 3：**-2 0** 1 -2 3 总和是|-2| + |0| = 2

可见，通过把 4 改成了 3，我们的步数变少了，少了 2 步

为什么有的时候会减少步数，有的时候会不变呢。分析一下，如果我们将一个数改变了，那么它和前一个数的差以及它和后一个数的差会一个变大 x，另外一个减小 x，所以当两个相邻的差一正一负的时候，改变之后可以正好让他们两个的正的减小 x，负的加上 x，这样我们就一共减掉了 2x 步  
不难想到，对于这一正一负的数来说，我们最多可以减掉 min(abs(正数)+abs(负数))×2 步

所以我们只要找到所有相邻的异号的两个差，然后找到他们中能减掉步数最多的那个，再和上面的改变第一个元素和改变最后一个元素比较一下，就可得出通过操作之前的改变任意一个数可以最多减掉多少操作步数，即为 m

然后最后的最少操作步数就等于本来需要的操作步数再减去 m

##### 代码 #####

#include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cmath>
    #define int long long
    using namespace std;
    signed main()
    { 
    	int T;
    	cin >> T;
    	while (T--)
    	{ 
    		int n;
    		cin >> n;
    		int t, r;
    		int a[n - 1];
    		cin >> t;
    		for (int i = 0; i < n - 1; i++)
    		{ 
    			cin >> r;
    			a[i] = r - t;
    			t = r;
    		}
    		int m = max(abs(a[0]), abs(a[n - 2]));
    		for (int i = 1; i < n - 1; i++)
    		{ 
    			if (a[i - 1] * a[i] < 0)
    			{ 
    				m = max(m, 2 * min(abs(a[i - 1]), abs(a[i])));
    			}
    		}
    		int sum = 0;
    		for (int i = 0; i < n - 1; i++)
    		{ 
    			sum += abs(a[i]);
    		}
    		cout << sum - m << endl;
    	}
    }

##### 以上 #####

ヾ(≧∪≦\*)ノ〃

[Link 1]: https://codeforces.com/contest/1453/problem/A
[16eb1d36b964ac83ad4d466ff2e3c63b.png]: /images/20221120/d08c15d33ae140869a3bdab3085d461c.png
[Link 2]: https://codeforces.com/contest/1453/problem/B