B. Most socially-distanced subsequence (Codeforces Round #649 Div. 2)

問題

https://codeforces.com/contest/1364/problem/B

問題概要

長さnの順列が与えられる。以下の条件を満たす長さkの配列を構築せよ。

• を順列pから作れるsのうちで最大にする
• 上記の条件を満たす配列sのうち、kの大きさを最小にする

考察

一番目の条件を満たすためには、差を最大としたいため、先頭と末尾を含む極大値と極小値を取ればよいです。

極大値と極小値の間にある項をどう扱うかですが、からが単調減少または単調増加のときは、中のが打ち消し合ってと同じになりますから、とっても取らなくても差が出ません。よって二番目の条件より、取らないほうがよいということになります。

結局、極大値と極小値だけを集めた配列が条件を満たす配列ということになります。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> p(n);
        for (int i = 0; i < n; i++) cin >> p[i];
        
        vector<int> ans{p[0]};
        for (int i = 1; i < n - 1; i++) {
            if ((p[i - 1] > p[i] and p[i] < p[i + 1]) or (p[i - 1] < p[i] and p[i] > p[i + 1])) {
                ans.emplace_back(p[i]);
            }
        }
        ans.emplace_back(p[n - 1]);
        cout << ans.size() << endl;
        for (auto x : ans) cout << x << " ";
        cout << endl;
    }
}