专栏首页用户6093955的专栏Sorted Adjacent Differences(CodeForces - 1339B)【思维+贪心】

Sorted Adjacent Differences(CodeForces - 1339B)【思维+贪心】

B - Sorted Adjacent Differences(CodeForces - 1339B)

题目链接

算法

思维+贪心

时间复杂度O(nlogn)

1.这道题的题意主要就是让你对一个数组进行一种特殊的排序,使得数组中相邻的两个数的差的绝对值成非递减趋势;

2.刚开始对这道题总是执拗于两个相等的数在不同位置,如何把它们放到前面这个问题,因为路走歪了,最终无果,没有思路。后来看了一些关于这道题的解题博客,豁然开朗。

3.使得数组中相邻的两个数的差的绝对值成非递减趋势,怎么想呢。单纯想怎么从差的绝对值最小到最大变化不太容易想,我们可以反过来想,怎么由差的绝对值最大到最小变化。什么时候差的绝对值最大,当然是数组中的最小值和最大值之间的差的绝对值最大。最小值和次大值之间的差的绝对值大还是最小值和次小值之间的差的绝对值大(或者最大值和次小值的差的绝对值大还是最大值和次大值的绝对值大),当然是前者。

4.然后在想接下来可能再小的是什么,当然是次小值和次大值之间的差的绝对值。以此类推,可以的出下面这个式子。

最小值、最大值、次小值、次大值、第三小值、第三大值、...
或者
最大值、最小值、次大值、次小值、第三大值、第三小值、...

注意上面的式子只是为了好理解才按照这个顺序写的,最终输出的时候不要忘了把它倒过来(不知道为啥请看题意)。

5.列出了式子后,那么思考一下什么时候才到头呢,即到哪里结束呢?

对于偶数个数的数组来讲,即最终达到处于中间的那两个数;

对于奇数个数的数组来讲,即最终到达处于中间的那一个数。

所以要特判一下。这也是为什么前面一开始就说要将题意倒过来想,否则直接想出从中间向两边展开这个思路不太容易。

6.所以最终得出的思路是先对数组排序,然后从中间向两边展开输出。

C++代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int t, n;
int a[N];
int main()
{
    cin >> t;
    while(t--)
    {
        cin >> n;
        for(int i = 0; i < n; i++)
            cin >> a[i];
        sort(a, a + n);
        /*
            n = 5
            0,1,2,3,4
            n = 4
            0,1,2,3
        */
        int l, r;
        if(n % 2 == 1)
        {
            cout << a[n/2] << " ";
            l = n / 2 - 1, r = n / 2 + 1;
        }
        else
            l = n / 2 - 1, r = n / 2;
        while(l >= 0 && r < n)
        {
            //cout << a[r] << " " << a[l] << " ";
            cout << a[l] << " " << a[r] << " ";
            //上面这两个式子用哪个都可以
            ++r;
            --l;
        }
        puts("");
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【软件18-循环队列及综合】

    F:将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量。存储在其中的队列称为循环队列(Circular Queue)。这种循环队列可以以单链表的方式来在...

    _DIY
  • 蓝桥杯突击复习准备——部分算法汇总

    当然,上面这个状态转移方程不适用于a数组长度较大的情况。比如AcWing896. 最长上升子序列 II (AC代码,思路在代码中)

    _DIY
  • 【Pet HDU - 4707 】【利用并查集找深度】

    _DIY
  • 遭遇DDoS攻击怎么防?

    导语| 最近几个月处理过多起DDoS攻击案例,从实际案例中总结了一些防护经验希望可以帮助到需要的同仁。本文主要分享DDoS攻击原理、以及实际攻击过程以及如何选择...

    持之以恒
  • DDOS-腾讯云DDOS

    是腾讯云面向所有用户推出的抗 DDoS 攻击的付费产品,支持任意源站位置,最高可达 900 Gbps 的 BGP 线路防护,能轻松有效应对 DDoS 、CC 攻...

    用户1361591
  • Leetcode 225. Implement Stack using Queues

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan
  • 冒泡排序法三部曲の(一)冒泡排序原理版

    思路分析: 经典的bubble sort(冒泡排序)原理类似于气泡上升过程,到自身的密度小于上一层介质则上升,排序同理。 以数组{5,4,3,2,1}为例: 第...

    根究FPGA
  • 0642-6.2-如何在CM界面创建触发器

    Fayson在这里先介绍下CM中的trigger,也就是触发器。触发器是当一个或多个特定条件得到满足的服务、角色、角色组、或主机将采取指定动作的声明。条件为ts...

    Fayson
  • 挑战程序竞赛系列(16):3.1最大化最小值

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • ubuntu蓝牙音响配对成功但在声音设置中无法设置 解决

    zhangrelay

扫码关注云+社区

领取腾讯云代金券