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)$