TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P5832
  • 题目
  • P5832砍树
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1s,256m
    问题描述

    何老板家门前有一排树,共 3 * N 棵 ,每棵树都有一定的高度,第i棵树高度为 \(h_i\)

    何老板需要添置家具,他雇你砍掉其中N棵树,剩下2*N棵。你可以砍掉其中任意N棵树,但何老板有个奇怪的要求,他希望剩下的树中,前N棵树的高度总和与后N棵树的高度总和之差,尽可能大
    请你计算出这个最大差值

    输入格式

    第一行,一个整数N
    第二行,3*N个空格间隔的整数,其中第i个数表示第i棵树的高度 \(h_i\)

    输出格式

    一个整数,即所求结果

    样例输入 1

    2
    3 1 4 1 5 9

    样例输出 1

    1

    样例解释:
    砍掉第2和第6棵树,剩下(3,4,1,5)
    差值为(3+4)-(1+5)=1

    样例输入 2

    1
    1 2 3

    样例输出 2

    -1

    样例输入 3

    3
    8 2 2 7 4 6 5 3 8

    样例输出 3

    5

    样例解释:
    砍掉第2第3和第9棵树

    提示

    对于60%的数据 \(1≤N≤10^3\)
    对于100%的数据 \(1≤N≤10^5\)
    \(1≤h_i≤10^9\)


    来源  ABC062D