转载

[转载] $CF652B$ 题解

阅读原文

写在前面:
虽然\(CF\)的题目存在恶意评分现象,但是题目本身还是很有意义的,尤其是一题多解,能够很好地训练我们的思维啦~

观察题目条件,

\(1.\)对所有的偶数\(i\)\(a_i >= a_{i-1}\)

\(2\).对所有的奇数\(i\)\(a_i <= a_{i-1}\)

那么,对于一个偶数位\(i\),它比左边\(i-1\)和右边\(i+1\)两个奇数位的值都要大或者相同。

由数学归纳法可得,所有偶数位上的数均大于等于奇数位上的数。

因此,对于一个给定的数列,我们可以将其从小到大排序,前面一半分给各个奇数位,后面一半分给各个偶数位。

对于“一半”这个说法,为了思路清晰可以对\(n\)的值进行分类讨论,分别赋值即可。

代码如下:

#include<bits/stdc++.h> using namespace std; inline int read() { int ret=0,f=1; char ch=getchar(); while(ch>'9'||ch<'0') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { ret=(ret<<1)+(ret<<3)+ch-'0'; ch=getchar(); } return ret*f; } int n,a[1005],ans[1005]; int main() { n=read(); for(register int i=1;i<=n;i++) a[i]=read(); sort(a+1,a+n+1); if(n%2==0) { for(register int i=1;i<n;i+=2) ans[i]=a[i/2+1]; for(register int i=2;i<=n;i+=2) ans[i]=a[n-i/2+1]; } else { for(register int i=1;i<=n;i+=2) ans[i]=a[i/2+1]; for(register int i=2;i<n;i+=2) ans[i]=a[n-i/2+1]; } for(register int i=1;i<=n;i++) printf("%d ",ans[i]); return 0; }

如有疑问,评论区见,感谢资瓷!

转载于:https://www.cnblogs.com/Peter0701/p/11302890.html

正文到此结束
本文目录