You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
67 lines
1.4 KiB
67 lines
1.4 KiB
#include <bits/stdc++.h>
|
|
|
|
using namespace std;
|
|
const int N = 1e6 + 10;
|
|
int a[N], b[N];
|
|
unordered_set<int> _set;
|
|
/*
|
|
4
|
|
1 3 4 2
|
|
|
|
答案：
|
|
2 2 3
|
|
*/
|
|
int cnt;
|
|
int main() {
|
|
int n;
|
|
scanf("%d", &n);
|
|
for (int i = 0; i < n; i++) {
|
|
scanf("%d", &a[i]);
|
|
b[a[i]]++;
|
|
_set.insert(a[i]);
|
|
}
|
|
|
|
while (true) {
|
|
sort(a, a + n); // 从小到大排序
|
|
int cx;
|
|
for (int i = 1; i < n; i++)
|
|
if (a[i] > a[0]) {
|
|
cx = i;
|
|
break;
|
|
}
|
|
|
|
b[a[0]]--;
|
|
if (b[a[0]] == 0) _set.erase(a[0]);
|
|
a[0] = a[cx]; // 最小调整为次小
|
|
b[a[cx]]++;
|
|
cnt++;
|
|
if (_set.size() < 3) break;
|
|
|
|
sort(a, a + n); // 从小到大排序
|
|
int cd;
|
|
for (int i = n - 2; i >= 0; i--)
|
|
if (a[i] < a[n - 1]) {
|
|
cd = i;
|
|
break;
|
|
}
|
|
b[a[n - 1]]--;
|
|
if (b[a[n - 1]] == 0) _set.erase(a[n - 1]);
|
|
a[n - 1] = a[cd]; // 最大调整为次大
|
|
b[a[cd]]++;
|
|
cnt++;
|
|
if (_set.size() < 3) break;
|
|
}
|
|
cout << cnt << " ";
|
|
for (int i = 0; i < n; i++)
|
|
if (b[i]) {
|
|
cout << i << " ";
|
|
break;
|
|
}
|
|
|
|
for (int i = n - 1; i >= 0; i--)
|
|
if (b[i]) {
|
|
cout << i << " ";
|
|
break;
|
|
}
|
|
return 0;
|
|
} |