1. 首页
  2. 代码宅, 动态规划(DP), 数据结构

【诸葛亮】

题目描述

YYY 每天研究天文学研究哲学,对于人生又有一些我们完全无法理解的思考。

在某天无聊学术之后,YYY 打开了http://web.sanguosha.com,准备用他心爱的诸葛亮虐人。进入了八人身份局,作为一位主公,YYY 果断选了诸葛亮,用诸葛亮挑7人。

YYY 为什么喜欢诸葛亮这个武将呢?因为观星是个很牛逼的技能。
观星——回合开始阶段,你可以观看牌堆顶的X张牌(X为存活角色的数量且最多为5),将其中任意数量的牌以任意顺序置于牌堆顶,其余则以任意顺序置于牌堆底。

可见观星这个技能如果用得好那么是可以知道对方所有牌的。于是YYY 把 7 个人全部轻松干掉。

虽然YYY 的观星永远能知道全场手牌,但是他想到了这样一个问题:正常的观星应该会发生什么呢?

假设每张牌能给诸葛亮带来一定收益,那么 YYY 现在想计算,某种特定情况下,诸葛亮观星带来的最大收益是多少。

但是 LCR 经过一年的思考,把这道题做出来了。YYY 觉得问题太简单了。他觉得,他都想了那么久,你怎么可能想出来?于是 YYY决定加强这个题。假设观星能观 n 张牌,对于每张牌都有一个收益 v[i],那么他现在要找到一些牌使他能获得的收益和最大。

但是LCR 经过两年的思考,把这道题做出来了。YYY觉得问题太简单了。他觉得,他都想了那么久,你怎么可能想出来?于是 YYY 决定加强这个题。他要求选取的那些牌需要是连续的。

但是 LCR 经过三年的思考,把这道题做出来了。YYY觉得问题太简单了。他觉得,他都想了那么久,你怎么可能想出来?于是YYY 决定加强这个题。根据他的哲学思想,他认为任何情况都是可能发生的,于是他决定不仅要算出最大收益,还要算出次大收益、第三大收益……直到第 k 大收益。他想,这下 zjr 这个傻逼应该做不出来了吧。

但是LCR 经过四年的思考,把这道题做出来了。YYY觉得问题太简单了。他觉得,他都想了那么久,你怎么可能想出来?于是 YYY决定加强这个题。他发现这个似乎是一道原题,于是他又加了一个条件,俗话说否极泰来,那么收益值就等于它的绝对值。

YYY 智商过于强大,不屑于想此等低端问题,然后你就要把这道题做出来。

输入格式

第一行包含一个整数 n,k。
接下来一行,包括 n 个整数,第 i 个数是 v[i]。

输出格式

输出共 k 行,每行包括一个整数,第 i 行的数表示第 i 大的收益。

样例数据 1

输入

5 2
1 2 -1 -1 3

输出

4
3

备注

【数据范围】
对于 10% 的数据,1≤n≤200。
对于 30% 的数据,1≤n≤2000。
对于 50% 的数据,1≤n≤100000,1≤k≤1000。
对于 100% 的数据,1≤n≤100000,1≤k≤n,-1000≤v[i]≤1000。

首先,可以计算出每个前缀和,然后对每个前缀和进行排序,此时如果用前k大前缀和与前k小前缀和相减再排序的话能拿50分(k太大TLE) 为了优化k,先列个表,其中上>下,左>右,例如:

f(0,n) f(0,n-1) f(0,n-2) … f(0,0)
f(1,n) f(1,n-1) f(1,n-2) … f(1,0)
f(2,n) f(2,n-1) f(2,n-2) … f(2,0)

其中f(a,b)代表sum[b]-sum[a],即区间[a+1,b]的收益和,根据表易得最右上的点永远是最大的,我们每次取出一个f(a,b)就将可能的次大解f(a+1,b),f(a,b-1)放入表中,维护一个优先队列即可,这样下来重复k次即可求得第k大的收益,代码还是比较容易实现。

哎,优先队列不熟悉,连50分都没推导到,写了个裸的FIFO拿了30分……感觉这些公式其实还是不难推,是自己没用心深入思考。

评分 0, 满分 5 星
0
0
看完收藏一下,下次也能找得到
上一篇:
:下一篇

2 条评论

gravatar

*

  1. YYY 1

    题目背景好像哪里不太对…

    #-49楼
    Google Chrome 43.0.2357.130Windows 7
    回复
    stdKonjac真是太蠢辣QAQ
    1. @YYY 很正常的呀

      Google Chrome 43.0.2357.132Windows 8.1
      回复
      stdKonjac真是太蠢辣QAQ