CF1189B-NumberCircle-趣味题

|

题目链接

原题面:

http://codeforces.com/contest/1189/problem/B

中文翻译:

https://www.luogu.org/problemnew/show/CF1189B

解析

突然发现太久没写题解了(其实是没写什么题)，思维能力感觉差了好多QAQ

题目要求我们做的非常简单，但一开始毫无头绪

突然想到按照化环为链的想法试图将问题简化一下

发现如果想要构造一个满足题目要求的序列非常简单，我们只要将原序列排序之后就行了(显然)

但是对于环上的情况就不一定满足，设从小到大排序后的数组为$b[]$,$b[1]+b[n-1]$也许并不能大于$b[n]$

,这时观察题中样例，猜测如果我们将$b[n-1]$和$b[n]$调换一下顺序是否使问题可行，答案是肯定的.

调换顺序后受影响的只有$b[1],b[n-1],b[n],b[n-2]$.现逐个证明这种做法的正确性

  • 显然$b[n-1]>=b[1]$故$b[n-1]+b[2]>b[1]$

  • $b[n]>=b[n-1]$故$b[n]+b[1]>b[n-1]$

  • $b[n-2]<=b[n]$,故$b[n]+b[n-3]>b[n-2]$

  • 最后我们只需判定一下是否$b[n-1]+b[n-2]<=b[n]$

    若是，则此数列无法满足要求

    反之能满足要求

所以做法就很简单了,将输入数列从小到大排序，然后将$b[n]$与$b[n-1]$互换判定一下就好了(提前判定是否可行当然可以)

Challenge

CF官方题解中说此题有$O(n)$做法，现在还mo有想到。。。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <cstdlib>
#define ri register int 
#define ll long long 
using namespace std;
const int maxn=100005;
const int inf=0x7fffffff;
int n,a[maxn],b[maxn];
int main(){
	int x,y;
	scanf("%d",&n);
	for(ri i=1;i<=n;i++)scanf("%d",&a[i]);
	sort(a+1,a+1+n);
	b[1]=a[1];
	b[n-1]=a[n];
	b[n]=a[n-1];
	for(ri i=2;i<=n-2;i++){
		b[i]=a[i];
	}
	for(ri i=2;i<=n-1;i++)if(b[i]>=b[i-1]+b[i+1]){
		puts("NO");
		return 0;
	}
	if(b[1]>=b[2]+b[n]){puts("NO");return 0;}
	if(b[n]>=b[1]+b[n-1]){puts("NO");return 0;}
	puts("YES");
	for(ri i=1;i<=n;i++)printf("%d ",b[i]);
	puts("");
	return 0;
}