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种形态的全部內容，希望文章能夠幫你解決所遇到的問題。

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