TRZ_2007 的博客

TRZ_2007 的博客

题解 AT3909 【Two Arrays】

posted on 2019-11-07 16:45:27 | under 题解 |

这道题目初来乍到可能会有些难看懂,于是下面给出思路。

Solution

首先观察题目,现在有两种操作:

  • 1:将 $a$ 集合中随机的一个值加上2

  • 2:将 $b$ 集合中一个随机的值加上1

首先想到用人类的智慧:

令 $x$ 为集合 $a$ 的总和, $y$ 为集合 $b$ 的总和。
$\because$ 集合 $a$ 一次性加的数比集合 $b$ 一次性加的数多
$\therefore$ 当 $x < y$ 时,必定可能有一次操作能使 $x = y$ ;反之则不然。

但是样例就否定了这种想法……

所以我们再一次仔细看题,发现:

  • 1:若 $a$ 集合中的这个值小于 $b$ 集合中的这个值,则增加 $a$ 集合中的数字,要使他们平等,需要加 $\dfrac{a_i-b_i}{2}$ 次。

  • 2:反着来,加 $a[i] - b[i]$ 次。

最后模拟即可。

code

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+10;

typedef long long ll;

ll a[N],b[N];
int n;
ll sum1,sum2;

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lld",a+i);//等同于scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) scanf("%lld",b+i);
    for(int i=1;i<=n;i++) {
        if(a[i] > b[i]) sum1 += (a[i] - b[i]);
        if(a[i] < b[i]) sum2 += (b[i] - a[i])/2;
    }
    if(sum1 <= sum2) puts("Yes");
    else puts("No");
}