题解 CF1419D2 【Sage's Birthday (hard version)】

onglu · 2020-09-20 08:26:10 · 题解

D. Sage's Birthday

题目大意

一个数可以被选择当且仅当这个数不是第1或第n个数并且这个数两边的数都比他大。
然后有一列数，你要给他们调换顺序，使得被选择的数最多。

思路

显然最好的情况就是一大一小一大一小。
因为假如把数列化成图像，那么一个凹型只有最底部的那个元素贡献答案。
于是我们看看能不能直接这样构造，排序，然后偶数位置的排最小的那些数，奇数位置排最大的那些数。
手算一下发现可以。
注意答案并不是(n-1)/2因为可能会有一下数是一样的，然后像555这样三个数就不计算贡献。
排列完数后统计答案输出即可。

代码

#include <bits/stdc++.h>
#define Mid ((l + r) >> 1)
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define ll long long
#define ull unsigned long long
#define FILL ""
using namespace std;
const int N = 0, M = 0;
int read(){
    char c; int num, f = 1;
    while(c = getchar(),!isdigit(c)) if(c == '-')f = -1; num = c - '0';
    while(c = getchar(), isdigit(c)) num = num * 10 + c - '0';
    return num * f;
}
int n, a[100009], vis[100009];
int main()
{
    //freopen(FILL".in", "r", stdin);
    //freopen(FILL".out", "w", stdout);
    n = read();
    for(int i = 1; i <= n; i++)a[i] = read();
    sort(a + 1, a + 1 + n);
    int now = 1;
    for(int i = 2; i <= n; i += 2)
        vis[i] = a[now++];
    for(int i = 1; i <= n; i += 2)
        vis[i] = a[now++];
    int ans = 0;
    for(int i = 2; i < n; i++){
        if(vis[i] < vis[i - 1] && vis[i] < vis[i + 1])ans++;
    }
    printf("%d\n",ans);
    for(int i = 1; i <= n; i++){
        printf("%d ",vis[i]);
    }
    printf("\n");
    return 0;
}