【每日一题】—— C. Challenging Cliffs（Codeforces Round 726 (Div. 2)）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【每日一题】—— C. Challenging Cliffs（Codeforces Round 726 (Div. 2)）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

🌏博客主页：PH_modest的博客主页
🚩当前专栏：每日一题
💌其他专栏：
🔴 每日反刍
🟡 C++跬步积累
🟢 C语言跬步积累
🌈座右铭：广积粮，缓称王！

一.题目描述

【每日一题】—— C. Challenging Cliffs（Codeforces Round 726 (Div. 2)）,每日一题,c语言,开发语言,codeforces,算法,学习

题目大意：

【每日一题】—— C. Challenging Cliffs（Codeforces Round 726 (Div. 2)）,每日一题,c语言,开发语言,codeforces,算法,学习

题目链接：

C. Challenging Cliffs（Codeforces Round 726 (Div. 2)）

二.思路分析

首先将给的数排序

然后找相邻两数绝对值最小的两个数（将他们的下标记为l和r），这两个数肯定是放在头和尾，因为题目要求是第一个和最后一个山峰绝对值最小

之后就剩下l前面的数和r后面的数了，这两组数都是已经排好序的（将前面一组记为P，后一组记为Q），也就是说他们都是困难程度最大的情况

接下来就面临两种选择，先放P后放Q，先放Q后放P，大部分人都觉得先放P后放Q更好，真的是这样的吗？

第二张图应该可以较为清楚的解释为什么这样较好，这里就不过多赘述了。

三.代码展示

#include<iostream>
#include<map>
#include<algorithm>
#include<cmath>

#define int long long

using namespace std;

int s[200020];

void solve()
{
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>s[i];
	}
	sort(s,s+n);
	int l=0,r=l+1;
	int mins=1e9;
	for(int i=0;i<n-1;i++)
	{
		if(s[i+1]-s[i]<mins)
		{
			mins=s[i+1]-s[i];
			l=i;
			r=i+1;
		}
	}
	cout<<s[l]<<" ";
	for(int i=r+1;i<n;i++)
	{
		cout<<s[i]<<" ";
	}
	for(int i=0;i<l;i++)
	{
		cout<<s[i]<<" ";
	}
	cout<<s[r]<<"\n";
}

signed main()
{
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}