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. int len = 1;
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. if (len == 1) {ans++;}
42. cout << "handing: " << cur.a << endl;
43. if (d.find(cur.a+1) != d.end()) {
44. cout << "found " << cur.a+1 << endl;
45. cur = *d.find(cur.a+1);
46.
47. d[cur.a-1]--;
48. if (d[cur.a-1] <= 0) {d.erase(cur.a-1);}
49.
50. len++;
51. } else {
53. d[cur.a]--;
54. if (d[cur.a] <= 0) {d.erase(cur.a);}
55. cur = *d.begin();
56. len = 1;
57. }
58. }
59.
60. cout << ans << endl;
61.
62. }
63.
64.
65.
66. int32_t main()
67. {
68. ios_base::sync_with_stdio(false);
69. cin.tie(NULL);
70. int t; cin >> t;
71. while (t--) {
72. solve();
73. }
74. return 0;
75. }
Success #stdin #stdout 0.01s 5356KB
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