題目

Given a permutation p of length n, find its subsequence s1, s2, …, sk of length at least 2 such that:

|s1?s2|+|s2?s3|+…+|sk?1?sk| is as big as possible over all subsequences of p with length at least 2.
Among all such subsequences, choose the one whose length, k, is as small as possible.
If multiple subsequences satisfy these conditions, you are allowed to find any of them.

A sequence a is a subsequence of an array b if a can be obtained from b by deleting some (possibly, zero or all) elements.

A permutation of length n is an array of length n in which every element from 1 to n occurs exactly once.

Input
The first line contains an integer$t(1\le t\le 2\times 10^4)$— the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $n(2\le n\le 10^5)$ — the length of the permutation p.

The second line of each test case contains n integers p1, p2, …, pn (1≤pi≤n, pi are distinct) — the elements of the permutation p.

The sum of n across the test cases doesn’t exceed 105.

Output
For each test case, the first line should contain the length of the found subsequence, k. The second line should contain s1, s2, …, sk — its elements.

If multiple subsequences satisfy these conditions, you are allowed to find any of them.

Example
Input
2
3
3 2 1
4
1 3 4 2
Output
2
3 1
3
1 4 2

思路

把這個(gè)排列想象成一個(gè)個(gè)長(zhǎng)條排放在坐標(biāo)軸上，如1，3，2 ，4
如此看來，不難看出要讓子數(shù)組相鄰數(shù)字的差的絕對(duì)值的和最大要遞增或遞減地去尋找，從第一個(gè)開始，放入子數(shù)組的第一位，往后若遞增（a[i]>a[i-1]），則一直往下尋找，直到出現(xiàn)轉(zhuǎn)折（a[i]<a[i-1]），再把a(bǔ)[i-1]放到子數(shù)組的下一個(gè)。若往后遞減也類似如此去尋找子數(shù)組里的各個(gè)數(shù)字。在這里插入代碼片

代碼

#include <iostream> #include <vector> #include <bits/stdc++.h> using namespace std;const int N=1e5+5;int a[N]; int sub[N];int main() {int t;scanf("%d",&t);int n;while(t--){scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&a[i]);}int temp=0;sub[temp++]=a[0];int i=1;while(i<n){if(a[i]<a[i-1]){while(a[i]<a[i-1] && i<n){i++;}sub[temp++]=a[i-1];}else{while(a[i]>a[i-1] && i<n){i++;}sub[temp++]=a[i-1];}}printf("%d\n",temp);for(int j=0;j<temp;j++){printf("%d ",sub[j]);}printf("\n");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的Most socially-distanced subsequence（贪心）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。