Codeforce 1536A-Omkar and Bad Story

題目連結:https://codeforces.com/problemset/problem/1536/A
題目大意:給定一個有$n$個元素的數列 <$A$>，求構造出一個數列 <$B$> 使得:
(1) $B$ 的 $size\leq300$
(2) $A$ 裡的元素至少都要在 $B$ 出現一次
(3) 對於所有的 $b_i,b_j$ ， $|b_i-b_j|$至少在 $B$ 出現一次
$-100 \leq A_i\leq100$

Solution

如果 $A$ 裡面的某個元素為負數，那麼我們絕對不可能構造出數列<$B$>，因為加絕對值後的數必為非負整數。
確定了<$A$>的元素都為非負整數後，那麼接著輸出 $0$ ~ $100$ 就好了，理由如下:
(1) 因為 $A$ 的最大可能值為 $100$，故 $0$ ~ $100$ 必可以包含 $A$ 的元素至少一次
(2) 假設 $b_i<b_j$ ，那麼 $b_i\leq |b_i-b_j|\leq b_j$，而 $A$ 的最大值為 $100$ ，最小值為 $0$，所以 $B=[0,1,2,…,100]$必定可以包含所有的$|b_i-b_j|$

Code

#include <bits/stdc++.h>
#define int long long
#define menhera_chan_is_mine ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
#define pi pair<int, int>
#define BE(i) i.begin(),i.end()
#define fi first
#define se second
#define INF 2147483647
#define mkp make_pair
#define ist insert
#define mod 1000000009
//#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
//#pragma GCC optimize("O2")
using namespace std;
int min(int a, int b){return a < b ? a : b;}
int max(int a, int b){return a > b ? a : b;}
bool isprime(int k){bool is=1 ; for ( int i = 2 ; i*i <= k ; i++ ) if ( k % i == 0 ) is = 0 ; return k>1?is:0;}
const double PI=acos(-1);
int n;
int a[105];
inline void sol(){
    cin >>n;
    for (int i=0;i<n;i++) cin >>a[i];
    bool flg=0;
    for (int i=0;i<n;i++){
        if (a[i]<0) flg=1;
    }
    if (flg) cout <<"NO\n";
    else {
        cout <<"YES\n101\n";
        for (int i=0;i<=100;i++)
            cout <<i<<" ";
        cout <<"\n";
    }
}
signed main(){
    menhera_chan_is_mine
    int _=1;
    cin >>_;
    while (_--) sol();
    return 0;
}

時間複雜度:$O(n)$