(挺丢人的, 看了editorial 也没把二分写对.)
贪心地讲, 我们可以把最小的 \(k\) 个元素放在局部最小值, 最大的 \(k+1\) 个元素放在相应的局部最大值. 问题在于有元素相等的情况下, 这个 \(k\) 的值并不方便确定. 注意到答案具有单调性(能有 \(k\) 个必然可以有 \(k-1\) 个), 而且如果给定 \(k\) 来验证能不能取到是简单的. 这样就可以二分答案.
二分的时候应当注意, 总是保持左端点 \(l\) 是满足性质的, 右端点 \(r\) 是不满足性质的, 总是要求 \(l<r-1\), 这样就可以在 \(r==l+1\) 的时候恰好退出, 保证答案就是 \(l\).
下面是代码.
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <stdint.h>
using namespace std;
inline void io_speed_up()
{
cin.tie(nullptr);
cin.sync_with_stdio(false);
cout.tie(nullptr);
}
#ifndef ONLINE_JUDGE
#define TRACE
#endif
#ifdef TRACE
#define trace(...) __trace__(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __trace__(const char *name, Arg1 &&arg1)
{
cout << "[#]";
cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __trace__(const char *names, Arg1 &&arg1, Args &&... args)
{
cout << "[#]";
const char *comma = strchr(names + 1, ',');
cout.write(names, comma - names) << " : " << arg1 << " | ";
__trace__(comma + 1, args...);
}
#else
#define trace(...) ;
#endif
const int MAXN = (int)1e5 + 5;
bool bin_search(vector<int> arr, int k, int n)
{
if (2 * k + 1 > n)
{
return false;
}
bool flag = true;
vector<int> b;
int u = 0, v = n - 1 - k;
for (int i = 0; i < 2 * k + 1; ++i)
{
if (i & 1)
{
b.emplace_back(arr[u++]);
}
else
{
b.emplace_back(arr[v++]);
}
}
for (int i = 1; i < 2 * k + 1; i += 2)
{
if (b[i] >= b[i + 1] || b[i] >= b[i - 1])
{
flag = false;
break;
}
}
return flag;
}
int main()
{
io_speed_up();
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i)
{
cin >> a[i];
}
sort(a.begin(), a.end());
int l = 0, r = n + 1;
int mid;
while (l < r - 1)
{
mid = (l + r) >> 1;
if (bin_search(a, mid, n))
{
l = mid;
}
else
{
r = mid;
}
}
int ans = l;
cout << ans << endl;
vector<int> b;
int u = 0, v = n - 1 - ans;
for (int i = 0; i < 2 * ans + 1; ++i)
{
if (i & 1)
{
b.emplace_back(a[u++]);
}
else
{
b.emplace_back(a[v++]);
}
}
for (int i = u; i < n - 1 - ans; ++i)
{
b.emplace_back(a[i]);
}
for (int i = 0; i < b.size(); ++i)
{
cout << b[i];
if (i < (int)b.size() - 1)
{
cout << " ";
}
}
cout << endl;
return 0;
}
Comments | NOTHING