A. Circular Local MiniMax
题目翻译:给我们一个数组(循环的也就是1和n是相邻的),我们可以对数组进行任意调序,对于每个数b[i]要求满足b[i] < b[i - 1] && b[i] < b[i + 1] 或者满足b[i] > b[i - 1] && b[i] > b[i + 1]。如果存在就输出yes并且输出构造的序列,否则输出no。
思路:我们考虑当一个数是波峰时,那么和他相邻的数一定是波谷,所以波峰波谷一定是交替出现的,所以当n是奇数时,最后一个数和第一个数是一样的,同为波峰或波谷,这样便和我们刚才所说的波峰波谷交替出现矛盾了。
至此我们考虑了一定无解的情况,
然后我们考虑当n为偶数时,我们很容易想到波峰就是较大的n/2个数,波谷就是较小的n/2个数,所以我们sort一遍,然后依次将前n/2个数的最小值,后n/2个数的最小值,前n/2个数的次小值,
后n/2个数的次小值,这样的顺序排列,构成序列,当然这里面也会有不合法的情况,我们需要再o(n)扫一遍。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
void run()
{
int n;
cin >> n;
for(int i = 1; i <= n; ++ i) scanf("%d", &a[i]);
int ans = 0;
if(n & 1)
{
puts("NO");
return;
}
else
{
sort(a + 1, a + 1 + n);
int now = 0;
int l = 1, r = n / 2 + 1;
for(int i = 0; i < n / 2; ++ i)
{
b[++ now] = a[l + i];
b[++ now] = a[r + i];
}
bool success = true;
for(int i = 1; i <= n; ++ i)
{
int l = i - 1, r = i + 1;
if(l == 0) l = n;
if(r == n + 1) r = 1;
if((b[l] > b[i] && b[r] > b[i]) || (b[l] < b[i] || b[r] < b[i]))
continue;
else
{
success = false;
break;
}
}
if(success)
{
puts("YES");
for(int i = 1; i <= n; ++ i) cout << b[i] << ' ';
cout << endl;
}
else puts("NO");
}
}
int main()
{
// freopen("1.in", "r", stdin);
int t;cin >> t;
while(t --) run();
return 0;
}
标签:int,div1A,个数,codeforces,波谷,波峰,&&,我们
From: https://www.cnblogs.com/cxy8/p/17365812.html