- 浏览: 37444 次
文章分类
- 全部博客 (41)
- 卧鸟个去 (2)
- Transform (2)
- Mathmatic (9)
- Plant-Tree (7)
- Data-Struct (12)
- Red-Black-Tree (1)
- Radix-Tree (1)
- Trie (2)
- String (4)
- BST (2)
- Amazing-Union-Find-Set (1)
- HDU (27)
- OJ (32)
- BFS (3)
- Pretty-Suffix-Array (2)
- POJ (6)
- Graceful-Segment-Tree (2)
- Geometry (6)
- Priority-Queue (2)
- Dynamic-Programing (1)
- DP (3)
- LCS (1)
- Convex-Hull (2)
- Triangulation (1)
- DFS (3)
- Combinatorial-Mathematics (2)
- Big-Number (1)
- Statistic (3)
- STL (1)
- Shortest-Path (3)
- ZOJ (1)
- Leftist-Tree (1)
- Prime (1)
- Binary-Index-Tree (1)
- (1)
- Stack (1)
- SPFA (0)
- CRT (1)
Time Limit: 3 Seconds Memory Limit: 65536 KB
Bernard Madoff is an American former stock broker, investment adviser, non-executive chairman of the NASDAQ stock market, and the admitted operator of what has been described as the largest Ponzi scheme in history.
Two programmers, Jerome O'Hara and George Perez, who helped Bernard Madoff program to produce false records have been indicted. They were accused of conspiracy, falsifying records of a broker dealer and falsifying records of an investment adviser.
In every quarter of these years, the two programmers would receive a data sheet, which provided a series of profit records a1 a2 ... aN in that period. Due to the economic crisis, the awful records might scare investors away. Therefore, the programmers were asked to falsifying these records into b1 b2 ... bN. In order to deceive investors, any record must be no less than all the records before it (it means for any 1 ≤ i < j ≤ N, bi ≤ bj).
On the other hand, they defined a risk value for their illegal work: risk value = | a1 - b1 | + | a2 - b2 | + ... + | aN - bN | . For example, the original profit records are 300 400 200 100. If they choose 300 400 400 400 as the fake records, the risk value is 0 + 0 + 200 + 300 = 500. But if they choose 250 250 250 250 as the fake records, the risk value is 50 + 150 + 50 + 150 = 400. To avoid raising suspicion, they need to minimize the risk value.
Now we will give you some copies of the original profit records, you need to find out the minimal possible risk value.
Input
There are multiple test cases (no more than 20).
For each test case, the first line contains one integer N (1 ≤ N ≤ 50000), the next line contains N integers a1 a2 ... aN (-109 ≤ ai ≤ 109). The input will end with N = 0.
Output
For each test case, print a single line that contains minimal possible risk value.
Sample Input
4 300 400 200 100 0
Sample Output
400
我地做浙大月赛果阵既一个题目,后来听101majia讲系用左偏树。
我之前研究堆果阵都有睇过下左偏树,其实就系二叉堆加上一个限制条件令到成个堆左偏,吾难理解。制定一个甘样既规则可以讲剩系得一个好处,合并快。尼条题既思路我系参照一个国家训练队关于左偏树既论文编写既,呢篇论文讲左偏树同埋例题证明既时候都唔错,但系讲到例题实现既时候,有两点令我捻左好耐。
一、点解输入既时候要dec(nd[i].key, i)?
二、点解要合并两个奇数堆既时候先删除堆顶元素?
第一个问题,其实尼条题目吾需要,因为答案系非严格递增,第二个问题我真系未明白点解,睇黎系维护中位数既关键。
其实睇左分析之后发觉尼条题目其实唔一定要用左偏树,因为数据结构唔要求动态,而且稳区间中位数即系稳区间第n/2大数,我地可以用划分、归并树代替。
下面贴上代码~
2608269 | 2011-07-31 15:45:34 | Accepted | 3512 | C++ | 280 | 968 | SGetEternal-_- |
#include <iostream> #include <cstdlib> #include <cstdio> using namespace std; #define MAXI 50011 struct LTT { struct node { int l, r, key, dis; }t[MAXI]; void clear(int n) { int i; for (i = 0; i <= n; i++) t[i].l = t[i].r = t[i].dis = -1; } int merge(int x, int y) { if (x == -1) return y; if (y == -1) return x; if (t[x].key < t[y].key) swap(x, y); t[x].r = merge(t[x].r, y); if (t[t[x].l].dis < t[t[x].r].dis) swap(t[x].l, t[x].r); t[x].dis = t[t[x].r].dis + 1; return x; } int delet(int x) { return merge(t[x].l, t[x].r); } }zkl; int main() { int n, i, j, k, pid[MAXI], tid[MAXI]; long long tsu; while (scanf("%d", &n), n) { zkl.clear(n); pid[0] = tid[0] = 0; for (i = j = 1; i <= n; i++, j++) { scanf("%d", &zkl.t[i].key); pid[j] = tid[j] = i; while (j > 1 && zkl.t[tid[j - 1]].key > zkl.t[tid[j]].key) { --j; tid[j] = zkl.merge(tid[j], tid[j + 1]); if (((pid[j + 1] - pid[j]) % 2 == 1 && (pid[j] - pid[j - 1]) % 2 == 1)) tid[j] = zkl.delet(tid[j]); pid[j] = pid[j + 1]; } } for (tsu = 0, i = 1; i < j; i++) for (k = pid[i - 1] + 1; k <= pid[i]; k++) tsu += abs(zkl.t[k].key - zkl.t[tid[i]].key); cout << tsu << endl; } return 0; }
尼条题目我地一开始仲以为同菲波那契有关,因为个题目名有Fin
发表评论
-
HDU 1370 Biorhythms
2011-08-03 10:27 1188Biorhythms Time Limit: 2000/10 ... -
HDU 1075 What Are You Talking About
2011-08-04 11:00 865What Are You Talking About Tim ... -
HDU 1058 Humble Numbers
2011-08-02 15:55 1215Humble Numbers Time Limit: 200 ... -
HDU 2095 find your present (2)
2011-08-02 16:13 813find your present (2) Time Lim ... -
HDU 1022 Train Problem I
2011-08-02 21:00 1012Train Problem I Time Limit: 20 ... -
2142 HDU box
2011-08-02 21:21 761box Time Limit: 3000/1000 MS ( ... -
HDU 2151 Worm
2011-08-01 20:48 842Worm Time Limit: 1000/1000 MS ... -
HDU 2722 Here We Go(relians) Again
2011-08-02 00:06 1025Here We Go(relians) Again Time ... -
HDU 3791 二叉搜索树
2011-08-02 14:26 1206二叉搜索树 Time Limit: 20 ... -
PKU 2352 Stars
2011-07-31 21:47 1024Stars Time Limit: 1000MS ... -
PKU 2774 Long Long Message
2011-07-31 21:26 901Long Long Message Time Li ... -
PKU 2777 Count Color
2011-07-31 21:31 793Count Color Time Limit: 1 ... -
HDU 2098 分拆素数和
2011-07-31 21:08 1061分拆素数和 Time Limit: 1000/1000 MS ... -
HDU 1798 Tell me the area .
2011-07-31 20:47 1118Tell me the area Time Limit: 3 ... -
HDU 2962 Trucking .
2011-07-31 20:46 678Trucking Time Limit: 20000/100 ... -
HDU 1596 find the safest road .
2011-07-31 20:45 600find the safest road Time Limi ... -
HDU 2553 N皇后问题 .
2011-07-31 20:20 702N皇后问题 Time Limit: 2000/1000 MS ... -
HDU 1392 Surround the Trees .
2011-07-31 20:19 793Surround the Trees Time Limit: ... -
HDU 1234 开门人和关门人 .
2011-07-31 20:17 671开门人和关门人 Time Limit: 2000/1000 ... -
HDU 1316 How Many Fibs? .
2011-07-31 20:15 975How Many Fibs? Time Limit: 200 ...
相关推荐
标题中的"ZOJ.gz_ ZOJ_ZOJ 1016_max flow_zoj 1045_zoj.rar" 提到了两个ZOJ(Zhejiang Online Judge)的题目,分别是1016和1045,这两个数字通常代表在线编程竞赛中的题目编号。这些题目通常涉及到算法和数据结构的...
zoj 3661 Palindromic Substring.md
zoj 1535 Lucky Ticket.md
zoj 3836 Circulation pipe.md
zoj 1404 Oil Pipeline.md
zoj 3114 Double Queue.md
zoj 1966 Etaoin Shrdlu.md
zoj 1179 Finding Rectangles.md
zoj 3051 Playing Poker.md
zoj 3109 Decode Message.md
zoj 1501 Knockout Tournament.md
zoj 1898 Discrete Logging.md
zoj 1433 Treasure Hunters.md
zoj 2009 Run Away.md
zoj 1472 Overlapping Shapes.md
zoj 3770 Ranking System.md
zoj 3811 Untrusted Patrol.md
zoj 1507 Crazy Search.md
zoj 2247 Magic Trick.md
zoj 3291 Never End.md