题目链接

牛客网竞赛 129583B

题意简述

有 张牌，初始牌堆为 ，目标牌堆为 。

允许的操作：选取相邻的两张牌，让它们同时 +1 或同时 -1。

问：能否通过若干次（包括 次）操作，使得 变成 （即 对所有 成立）？

数据范围：，，多组测试。

思路

从左到右贪心模拟：为了让 变成 ，只能调整 这对相邻牌。把差值 加到 和 上。最后检查 是否等于 。

为什么这样是对的？

  1. 操作的特点：每次操作必须同时改变相邻的两个数，且改变量相同（都 +1 或都 -1）。
  2. 从最左边开始想：
    • 要让 变成 ，只能通过操作 来实现。
    • 我们需要给 加上 ，同时 也会被加上相同的值。
    • 这样 就匹配了 ，但 被改变了。
  3. 接着看 ：
    • 此时 已经变成了 。
    • 为了让 变成 ，我们只能操作 ，给 加上差值 。
    • 这个差值也会加到 上。
  4. 依次类推：
    • 每次我们只关心当前这个位置 能否匹配 。
    • 匹配的方法就是让 和 同时加上 （这个 是当前的值，可能已经被前面的操作修改过）。
    • 这样 就匹配了 ，而差值被“传递”给了 。
  5. 最后一步：
    • 当我们处理到 时，会调整 。
    • 调整后 匹配了 ， 被改变了。
    • 最后只需要检查 是否恰好等于 。
    • 如果相等，说明整个过程可行；否则不可行。

算法步骤（直接对应代码）

for i = 1 to n-1:
    diff = b[i] - a[i]      // 当前差值
    a[i] += diff            // 当前位匹配
    a[i+1] += diff          // 差值传递给下一位

检查 a[n] == b[n] 是否成立

代码实现

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef unsigned long long ull;
typedef long long ll;
int a[100006];
int b[100006];
int s[100006];
void solve()
{ 
	int n;
	cin>>n;
	
	for(int i=0;i<n;i++)cin>>a[i];
	for(int i=0;i<n;i++)cin>>b[i];
	for(int i=0;i<n-1;i++){
        int diff=b[i]-a[i];
        a[i]+=diff;
        a[i+1]+=diff;
    }
    if(a[n-1]==b[n-1])cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

int main()
{
	#ifndef ONLINE_JUDGE
    freopen("0.txt", "r", stdin);
    #endif
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--)solve();
	return 0;
}

复杂度

  • 时间：，一次遍历。

关键点

  • 操作只能同时改变相邻两数，所以每个位置的调整都会影响下一个位置。
  • 贪心：从左到右，先保证当前位正确，把问题“推给”下一位。
  • 最后一位是检验标准：如果所有前面的调整刚好让最后一位也匹配，那么整个方案就可行。

一句话总结

从左到右依次调整，让每个位置匹配目标值，把差值传递给右边，最后检查最后一个位置是否自动匹配。

补充

可以发现这道题背后有一个优雅的数学性质：交错和不变。

定义一个数组的交错和为：奇数位元素之和 - 偶数位元素之和。 当给相邻的两项 ai和 ai+1同时 +1时，由于一个是奇数位，一个是偶数位，所以“奇数位和”与“偶数位和”会同时增加 1。 因此，它们的差值（交错和）永远保持不变！

所以，a 能变到 b 的充分必要条件其实就是：数组 a的交错和 等于 数组 b 的交错和。