CF2106C Cherry Bomb

· · 题解

题目传送门

思路

不难发现，本题可以分为两种情况。

  1. 当 b 数组全都是 -1。我们可以发现 b 数组最大数最小的情况为 a 数组的最大数减去最小数。而 b 数组最大数最大为 k。所以此时答案为 k-(maxx-minx)+1，maxx 表示 a 数组的最大数，minx 表示 a 数组的最小数。
  2. 当 b 数组有一个不是 -1。那么答案只有可能是 0 或 1。当 b 数组中未知的数超出了 0 \sim k 的范围或存在四个数 a_i+b_i \ne a_j+b_j 且 b_i 和 b_j 都不为 -1 时答案就为 0，否则答案为 1。

    AC Code：

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int a[N];
int b[N];
void solve()
{
    int n,k;
    cin >>n>>k;
    for(int i=1;i<=n;i++) cin >>a[i];
    for(int i=1;i<=n;i++) cin >>b[i];
    bool flag=1;
    for(int i=1;i<=n;i++)
    {
        if(b[i]!=-1)
        {
            flag=0;
            break;
        }
    }
    if(flag)
    {
        int maxx=0,minx=2e9;
        for(int i=1;i<=n;i++)
        {
            maxx=max(maxx,a[i]);
            minx=min(minx,a[i]);
        }
        cout <<k-(maxx-minx)+1<<'\n';
    }
    else
    {
        int sum=-1;
        for(int i=1;i<=n;i++)
        {
            if(b[i]!=-1)
            {
                int ans=a[i]+b[i];
                if(sum==-1) sum=ans;
                else
                {
                    if(sum!=ans)
                    {
                        cout <<0<<'\n';
                        return ;
                    }
                }
            }
        }
        for(int i=1;i<=n;i++)
        {
            int bb=sum-a[i];
            if(bb<0 || bb>k)
            {
                cout <<0<<'\n';
                return ;
            }
        }
        cout <<1<<'\n'; 
    }
}
int main()
{
    int t;
    cin >>t;
    while(t--)
    {
        solve();
    }
    return 0;
}