题意
Split a unique array into two almost unique arrays. unique arrays指数组各个数均不相同，almost unique arrays指可以删掉
数后再判断。
思路
略神的数学构造题。。。 官方题解： An equivalent definition for
almost unique, is arrays with at least ⌊ 2
n / 3⌋ different elements. The idea is to split
s into three parts. In the first part, we give uniqueness to
a. In the second part, we give uniqueness to
b. In the third part, we give uniqueness to both. Lets assume
s is sorted. Since
s is an unique array,
s
i ≥
i for all
i (0-based). The image below will give some intuition on how to split it.
ais red,
b is blue, the length of the bar represent the magnitude of the number. In the first and second part, we do not care about the array that we are not giving uniqueness to.
We will make an example with
n = 30.
i = 0... 9: assign
a
i =
i (do not care values of
b)
i = 10... 19: assign
b
i =
i (do not care values of
a)
i = 20... 29: assign
b
i = 29 -
i.
a takes the remains. From
i = 20,
a will have strictly increasing values starting from at least 11.
代码
[cpp] #include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <string> #include <cstring> #include <vector> #include <set> #include <stack> #include <queue> #define MID(x,y) ((x+y)/2) #define MEM(a,b) memset(a,b,sizeof(a)) #define REP(i, begin, end) for (int i = begin; i <= end; i ++) using namespace std; typedef long long LL; struct num{ int value; int id; num(){} num(int _id, int _value){id = _id; value = _value;} }; bool cmp(num n1, num n2){ return n1.value < n2.value; } typedef vector <num> VI; VI v; int a[100005], b[100005]; int main(){ //freopen("test.in", "r", stdin); //freopen("test.out", "w", stdout); int n; scanf("%d", &n); REP(i, 0, n-1){ int tmp; scanf("%d", &tmp); v.push_back(num(i, tmp)); } sort(v.begin(), v.end(), cmp); int d = (int)ceil((double)n/3); for (int i = 0; i < min(n, d); i ++){ a[v[i].id] = i; b[v[i].id] = v[i].value - a[v[i].id]; } for (int i = d; i < min(n, d*2); i ++){ b[v[i].id] = i; a[v[i].id] = v[i].value - b[v[i].id]; } for (int i = 2*d; i < n; i ++){ b[v[i].id] = n - 1 - i; a[v[i].id] = v[i].value - b[v[i].id]; } puts("YES"); for (int i = 0; i < n-1; i ++) printf("%d ", a[i]); printf("%d\n", a[n-1]); for (int i = 0; i < n-1; i ++) printf("%d ", b[i]); printf("%d\n", b[n-1]); return 0; } [/cpp]
