[codeforces 1364B] Most socially-distanced subsequence 绝对值脱壳的4种形态

Codeforces Round #649 (Div. 2)  参与排名人数11286

[codeforces 1364B]   Most socially-distanced subsequence   绝对值脱壳的4种形态

总目录详见https://blog.csdn.net/mrcrack/article/details/103564004

在线测评地址https://codeforces.com/contest/1364/problem/B

ProblemLangVerdictTimeMemory

B - Most socially-distanced subsequence	GNU C++17	Accepted	46 ms	800 KB

题目大意：给定数组a,可以删除任意元素，要求剩下的元素，相邻差值绝对值和最大，对应的剩下元素的个数最少，输出最少个数。

|x-y|+|y-z|

1.|x-y|脱壳情况如下

x>=y,|x-y|=x-y

x<=y,|x-y|=y-x

2.|y-z|脱壳情况如下

y>=z,|y-z|=y-z

y<=z,|y-z|=z-y

3.|x-y|+|y-z|脱壳情况如下

有4种组合

x>=y,y>=z

|x-y|+|y-z|=x-y+y-z=x-z此种情况，可删除元素y

x>=y,y<=z

|x-y|+|y-z|=x-y+z-y=x+z-2*y

x<=y,y>=z

|x-y|+|y-z|=y-x+y-z=2*y-(x+z)

x<=y,y<=z

|x-y|+|y-z|=y-x+z-y=z-x此种情况，可删除元素y

按上述思路，采用栈(在连续数据中，有目的的选取部分数据，用栈比较合适)的方式，编写的AC代码如下

#include <stdio.h> #define maxn 100010 int a[maxn],st[maxn],top; void solve(){int i,x,y,z,n;scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&a[i]);top=0;for(i=1;i<=n;i++){while(top>=2){x=st[top-1],y=st[top],z=i;if((a[x]>=a[y]&&a[y]>=a[z])||(a[x]<=a[y]&&a[y]<=a[z]))top--;else break;}st[++top]=i;}printf("%d\n",top);for(i=1;i<=top;i++)printf("%d ",a[st[i]]);printf("\n"); } int main(){int t;scanf("%d",&t);while(t--)solve();return 0; }

按上述思路，采用再开一个数组用来存储剩下的数组元素，对应的AC代码，建议读者不用细读，只是告诉读者掌握数据结构有多么重要，懂和不懂，同一个思路，编出的代码差太多了。

ProblemLangVerdictTimeMemory

B - Most socially-distanced subsequence	GNU C++17	Accepted	62 ms	1900 KB

#include <stdio.h> #define maxn 100010 int a[maxn],b[maxn],l[maxn],r[maxn],vis[maxn]; void solve(){int n,i,x,y,z,ans,j;scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&a[i]);for(i=1;i<=n;i++)vis[i]=0;if(n==2){printf("2\n");for(i=1;i<=n;i++)printf("%d ",a[i]);printf("\n");return ;}l[2]=1,y=2,r[2]=3,j=0;while(y+1<=n){//n>=3if((a[l[y]]>=a[y]&&a[y]>=a[r[y]])||(a[l[y]]<=a[y]&&a[y]<=a[r[y]])){y++;l[y]=l[y-1],r[y]=y+1;if(!vis[l[y-1]])vis[l[y-1]]=1,b[++j]=a[l[y-1]];}else{if(!vis[l[y]])vis[l[y]]=1,b[++j]=a[l[y]];if(!vis[y])vis[y]=1,b[++j]=a[y];y++,l[y]=y-1,r[y]=y+1;;}}b[++j]=a[y];printf("%d\n",j);for(i=1;i<=j;i++)printf("%d ",b[i]);printf("\n"); } int main(){int t;scanf("%d",&t);while(t--)solve();return 0; }

 

总结

以上是生活随笔为你收集整理的[codeforces 1364B] Most socially-distanced subsequence 绝对值脱壳的4种形态的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。