B. Most socially-distanced subsequence

題意：
給出一個數組$a$，找到數組中的一個子序列$s$(長為$x$)，滿足“${\sum }_{i=1}^x|s[i]?s[i?1]|$最大”。如果有多個答案就出$x$較小的子序列

思路：
我們觀察一個遞增的序列$s=\{1，2，3，4，6\}$，則：
${\sum }_{i=1}^x|s[i]?s[i?1]|=5$，因為$s[i]>s[i?1]$，所以當我們拆開公式，發現只剩下$s[5]?s[1]=6?1=5$，同理當序列遞減也有同樣的結論。(解決了最短的問題)。

序列$\{x,z,y\}$，如果在數軸上$z$在$x，y$中間(如$z_1$)，$|y?z|+|z?x|=y?x$，如果像$z_2$一樣，我們可以發現$|y?z|+|z?x|=z?y+z?x$，這個找到${\sum }_{i=1}^x|s[i]?s[i?1]|$最大和$x$最小用到的方法都是一樣的。

剩下的就是我們的模擬了，找出數組a中連續的遞增或遞減的序列，除去中間的元素，不影響結果。

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5+10; const int inf = 0x7ffffff; const ll INF = 0x7fffffffffff; ll f[][2] = {1, 0, 0, 1, -1, 0, 0, -1}, n, m; ll s[N]; int read() {int x = 0; int f = 1; char s = getchar();while(s < '0' || s > '9') {if(s == '-') f = -1; s = getchar();}while(s >= '0' && s <= '9') {x = (x << 3) + (x << 1) + s - 48; s = getchar();}return x * f; } int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);int t;cin >> t;while(t--) {n = read();m = n;for(int i=1; i<=n; i++) s[i] = read();if(n == 2) {cout << 2 << endl;for(int i=1; i<=n; i++) cout << s[i] << ' ';cout << endl; continue;}int i = 1, j = 2, k = 3;//從數組下標1，2，3開始掃描，每三個三個比較。while(k <= n) {//判斷是否連續遞增或if(s[j]>s[i] && s[k]>s[j] || s[j]<s[i] && s[j]>s[k]) {m--;s[j] = -1;/做標記。j++, k++;}else i = j, j++, k++;}cout << m << endl;for(int i=1; i<=n; i++) {if(s[i] != -1) cout << s[i] << ' ';}cout << endl;}return 0; }

總結

以上是生活随笔為你收集整理的B. Most socially-distanced subsequence(思维+模拟)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。