Editorial for Bedao Mini Contest 08 - CHECKARRAY


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Giả sử ~a[i] \ge a[j]~. Ta có ~a[i] - a[j] \le 1~.

Có ~a[i] - a[j] = 0~, dễ thấy điều kiện này chỉ thỏa mãn khi ~a[i] = a[j]~. Vì vậy ta có thể chọn mọi cặp ~(i, j)~ với ~a[i] = a[j]~ và loại bỏ ~a[j]~. Sau đó, ta thu được một dãy các số phân biệt đôi một.

Có ~a[i] - a[j] = 1~, dễ thấy nếu sắp xếp lại dãy thu được trên, để thu dược dãy này về ~1~ phần tử, dãy đó phải tăng dần với hiệu hai số liên tiếp bằng ~1~. Ta thu dãy về ~1~ phần tử bằng cách chọn liên tiếp hai số bé nhất và loại bỏ số bé hơn.

Code mẫu

#include <iostream>
#include <stdio.h>
#include <vector>
#include <cmath>
#include <math.h>
#include <map>
#include <algorithm>
#include <set>
#include <bitset>
#include <queue>
#include <cstring>
#include <stack>
#include <iomanip>
#include <assert.h>

#define BIT(x,pos) (((x)>>(pos)) & 1LL)
#define _(x) (1LL<<(x))
#define bitCnt(x) __builtin_popcountll(x)
#define turnOn(x,pos) ((x) = (_(pos)))
#define turnOff(x,pos) ((x) &= ~(_(pos)))
#define flipBit(x,pos) ((x) ^= (_(pos)))
#define lowBit(x) ((x) & (-x))
#define turnAll(x) (_(x)-1LL)

#define name "test"
#define nameTask ""
#define fastIO ios::sync_with_stdio(false); cin.tie(0);

using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;

const int N = 50;

vector<int> a;
int n;

int main()
{
    if (fopen(name".INP","r"))
        freopen(name".INP","r",stdin),
        freopen(name".OUT","w",stdout);

    fastIO

    cin>>n;

    for (int i = 1;i <= n; ++i)
    {
        int x;
        cin>>x;
        a.push_back(x);
    }

    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());

    for (int i = 1;i < (int)a.size(); ++i)
        if (a[i] != a[i-1] + 1) return cout<<"NO" ,0;

    cout<<"YES";
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.