第12屆北師大校賽熱身賽第二場 A.不和諧的長難句1不和諧的長難句1

題目連結：http://www.bnuoj.com/bnuoj/problem_show.php?

pid=17121

2014-04-25 22:59:49

Time Limit: 8000ms

Case Time Limit: 2000ms

Memory Limit: 65536KB

64-bit integer IO format: %lld      Java class name: Main

Font Size: + -

Type:   None Graph Theory      2-SAT     Articulation/Bridge/Biconnected Component      Cycles/Topological Sorting/Strongly Connected Component      Shortest Path          Bellman Ford         Dijkstra/Floyd Warshall      Euler Trail/Circuit      Heavy-Light Decomposition      Minimum Spanning Tree      Stable Marriage Problem      Trees      Directed Minimum Spanning Tree      Flow/Matching         Graph Matching              Bipartite Matching              Hopcroft–Karp Bipartite Matching              Weighted Bipartite Matching/Hungarian Algorithm          Flow              Max Flow/Min Cut              Min Cost Max Flow  DFS-like     Backtracking with Pruning/Branch and Bound      Basic Recursion      IDA* Search     Parsing/Grammar      Breadth First Search/Depth First Search      Advanced Search Techniques          Binary Search/Bisection          Ternary Search  Geometry      Basic Geometry     Computational Geometry      Convex Hull      Pick's Theorem Game Theory      Green Hackenbush/Colon Principle/Fusion Principle      Nim      Sprague-Grundy Number  Matrix     Gaussian Elimination      Matrix Exponentiation  Data Structures      Basic Data Structures      Binary Indexed Tree      Binary Search Tree      Hashing     Orthogonal Range Search      Range Minimum Query/Lowest Common Ancestor      Segment Tree/Interval Tree      Trie Tree      Sorting     Disjoint Set  String      Aho Corasick     Knuth-Morris-Pratt      Suffix Array/Suffix Tree  Math      Basic Math     Big Integer Arithmetic      Number Theory          Chinese Remainder Theorem          Extended Euclid          Inclusion/Exclusion          Modular Arithmetic      Combinatorics         Group Theory/Burnside's lemma          Counting      Probability/Expected Value  Others     Tricky      Hardest     Unusual      Brute Force      Implementation     Constructive Algorithms      Two Pointer      Bitmask     Beginner      Discrete Logarithm/Shank's Baby-step Giant-step Algorithm      Greedy      Divide and Conquer  Dynamic Programming                    Tag it!

某L近期很苦逼地在看一本叫做《雞阿姨&雞瑪特 閱讀難句教程》的書，這本書的主要内容就是解說一堆奇怪的難懂的無比冗長同一時候又讓人看了想睡覺的“長難句”，每一個句子中都有無數不認識的單詞外加倒裝、省略、插入語、複雜修飾、和固定搭配。然後還總是讓人看到暈頭轉向都看不到一個句号。

但更讓人糾結的是，在這麼BT的前提下，竟然還有些句子由于排版原因被分在了兩頁（即前一頁的最後幾行和後一頁的前幾行），這讓某L非常惱火，于是他開始觀察這本書的排版方式【這關注點真偏— —||】，他發現。這本書的結構事實上非常easy。書中共同擁有N（N<=10^6）個小段，每段包含一個帶有編号長難句和其相應的解說。每一個長難句都占5行（包含其編号），而編号為i的長難句相應的解說占a[i]行。

排版順序則是依照長難句的編号由小到大。每一個長難句之後緊接着就是其相應的解說。然後再緊跟着下一個長難句和其相應的解說……由于書中每一頁最多僅僅能排30行内容。是以導緻了上述悲劇的發生。

為了解決問題。某L想在每一個小段中間加上一些空行（當然也能夠不加）。使得全部的長難句都在同一頁内。那麼他最少須要加多少個空行呢=，=

一個整數N，表示一共同擁有N的小段

接下來N行，每行兩個數m、a[m]。表示編号為m的長難句相應的解說占a[m]行。

0<N<=10^6

1<=m<=N，而且不會反複

a[m]為int型正整數。

一個整數P。表示最少須要加入的空行的數目

輸入量巨大。請使用scanf，使用cin的話可能TLE。

也是水題一道。。。

隻是比賽的時候沒想出來，後來才AC的。

。。設m為上次沒放完的那一部分則 m=(m+5+a[i])%30,則30-m即為這次應該加上的行數，隻是這樣的算法會把最後一頁的也加上，是以要扣掉

本文轉自mfrbuaa部落格園部落格，原文連結：http://www.cnblogs.com/mfrbuaa/p/5262327.html，如需轉載請自行聯系原作者