P2125 图书馆书架上的书

    • 207通过
    • 389提交
  • 题目提供者 邵逸
  • 评测方式 云端评测
  • 标签 数论,数学 模拟 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    NOIP2014即将来临,JC书院信息学兴趣小组也在积极准备着,于是乎usqwedf、梁大大、畜牧办专场、YH大神和LHT大神也要推出“蓝翔杯”。

    在图书馆、MC等大神们相继举办了JC书院联合竞赛“弃疗杯”“UID #3”,据说YH大神还要苦苦钻研网络流的JC书院13届13班的WZF神牛和MZC神牛听到这个消息后决定联袂打造“十三点杯”。但是出一套题目是一项繁重的工作,于是他们决定再拉上和他们同届并且同班还同为JC书院信息学兴趣小组成员同时也在图书馆正在找“Hello_World”标程的蒟蒻SY。

    可怜的蒟蒻SY因为还要写一大堆的作业,怎么也不肯答应,终于WZF神牛妥协说:“我来出一道题,你要是做出来了我们就不让你出题,否则……你懂的。”蒟蒻SY才刚看完WZF神牛即兴出的题目,便带着哭腔对WZF神牛说:“你们赢了。”

    可是蒟蒻SY实在是太弱了,根本不会出题,他绞尽脑汁,终于想到了一个办法——将WZF神牛出的题目copy一下。

    题目描述

    图书馆有n个书架,第1个书架后面是第2个书架,第2个书架后面是第3个书架……第n-1个书架后面是第n个书架,第n个书架后面是第1个书架,第i个书架上有b[i]本书。现在,为了让图书馆更美观,WZF神牛让蒟蒻SY搬动书架上的书,使每个书架上的书一样多。由于搬动的书可能会很多,所以蒟蒻SY只能将一个书架上的书搬到与其相邻的两个书架上。那么蒟蒻SY最少搬动几本书呢?

    输入输出格式

    输入格式:

    共2行,第1行1个正整数n,第2行n个非负整数,第i个为b[i]。

    输出格式:

    共n+1行,第1行1个正整数m,表示蒟蒻SY最少搬动m本书,之后n行(即第2行至第n+1行)每行2个整数,第i行有两个整数af[i]和ab[i],分别表示蒟蒻SY要将第i个书架上的af[i]本书和ab[i]本书分别搬到它前面的一个书架上和它后面的一个书架上。

    输入输出样例

    输入样例#1: 复制
    5
    15 7 11 3 14
    
    输出样例#1: 复制
    12
    2 3
    -3 0
    0 1
    -1 -6
    6 -2
    

    说明

    n<=5000001(为保证有唯一解,n必为奇数),b[i]<= 21474803648(蒟蒻SY:俺当初一看到这儿就想哭。)

    若af[i]为负数,则说明蒟蒻SY要把第i个书架前面的那个书架上的-af[i]本书搬到第i个书架上。

    同理,若ab[i]为负数,则说明蒟蒻SY要把第i个书架后面的那个书架上的-ab[i]本书搬到第i个书架上。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。