1. #include <bits/stdc++.h>
2. using namespace std;
4. #define ll long long
5. #define nL "\n"
6. #define pb push_back
7. #define mk make_pair
8. #define pii pair<int, int>
9. #define a first
10. #define b second
11. #define vi vector<int>
12. #define all(x) (x).begin(), (x).end()
13. #define umap unordered_map
14. #define uset unordered_set
15. #define MOD 1000000007
16. #define imax INT_MAX
17. #define imin INT_MIN
18. #define exp 1e9
19. #define sz(x) (int((x).size()))
20.
21.
22. void solve() {
23. int n; cin >> n;
24. map<ll,ll> d;
25.
26. for(auto i = 0; i < n; i++) {
27. ll o; cin >> o;
28. if (d.find(o) != d.end()) {
29. d[o]++;
30. } else {d[o] = 1;}
31. }
32.
33. int ans = 0;
34.
35.
36. pair<ll,ll> cur = *d.begin();
37. d[cur.a]--;
38. if (d[cur.a] <= 0) {d.erase(cur.a);}
39.
40. while((int)d.size() != 0) {
41. cout << "handing: " << cur.a << endl;
42. if (d.find(cur.a+1) != d.end()) {
43. cout << "found " << cur.a+1 << endl;
44. cur = *d.find(cur.a+1);
45.
46. d[cur.a-1]--;
47. if (d[cur.a-1] <= 0) {d.erase(cur.a-1);}
48. } else {
50. ans++;
51. d[cur.a]--;
52. if (d[cur.a] <= 0) {d.erase(cur.a);}
53.
54. cur = *d.begin();
55. }
56. }
57.
58. cout << ans << endl;
59.
60. }
61.
62.
63.
64. int32_t main()
65. {
66. ios_base::sync_with_stdio(false);
67. cin.tie(NULL);
68. int t; cin >> t;
69. while (t--) {
70. solve();
71. }
72. return 0;
73. }
Success #stdin #stdout 0.01s 5548KB
stdin
10
6
2 2 3 4 3 1
5
11 8 7 10 9
6
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
8
1 1 4 4 2 3 2 3
6
1 2 3 2 3 4
7
10 11 11 12 12 13 13
7
8 8 9 9 10 10 11
8
4 14 5 15 6 16 7 17
8
5 15 6 14 8 12 9 11
5
4 2 2 3 4
stdout
handing: 1
found 2
handing: 2
found 3
handing: 3
found 4
handing: 4
handing: 2
found 3
handing: 3
2
handing: 7
found 8
handing: 8
found 9
handing: 9
found 10
handing: 10
found 11
handing: 11
1
handing: 1000000000
handing: 1000000000
handing: 1000000000
handing: 1000000000
handing: 1000000000
5
handing: 1
found 2
handing: 2
found 3
handing: 3
found 4
handing: 4
handing: 2
found 3
handing: 3
found 4
handing: 4
2
handing: 1
found 2
handing: 2
found 3
handing: 3
found 4
handing: 4
handing: 2
found 3
handing: 3
2
handing: 10
found 11
handing: 11
found 12
handing: 12
found 13
handing: 13
handing: 11
found 12
handing: 12
found 13
handing: 13
2
handing: 8
found 9
handing: 9
found 10
handing: 10
found 11
handing: 11
handing: 9
found 10
handing: 10
2
handing: 4
found 5
handing: 5
found 6
handing: 6
found 7
handing: 7
handing: 14
found 15
handing: 15
found 16
handing: 16
found 17
handing: 17
2
handing: 5
found 6
handing: 6
handing: 8
found 9
handing: 9
handing: 11
found 12
handing: 12
handing: 14
found 15
handing: 15