[Codeforces 1141.C] Polycarp Restores Permutation

原题

思路

  1. 排列的特征:最小值=1,最大值=n,不重不漏
  2. 给定任意初始值,按照q恢复出的数组若满足:最大-最小==n-1,且没有重复元素。即可恢复为1~n的一个排列(平移)。Hashset,$O(n)$。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/*
* https://codeforces.com/problemset/problem/1141/C
* C. Polycarp Restores Permutation
*/
#include <bits/stdc++.h>
using namespace std;
/*
* Solution goes here.
*/
vector<int> restorePermutation(int n, vector<int>& diff) {
unordered_set<int> mem {0};
int val = 0, min_v = 0, max_v = 0;
for (auto& v : diff) {
val += v;
auto r = mem.insert(val);
if (!r.second) return {-1};
min_v = min(min_v, val);
max_v = max(max_v, val);
if (max_v - min_v > n - 1) return {-1};
}
val = 1 - min_v;
vector<int> res {val};
for (auto& v : diff) {
val += v;
res.push_back(val);
}
return res;
}