鍍金池/ 問(wèn)答/人工智能  C++  網(wǎng)絡(luò)安全  HTML/ 一道hihocoder的編程題

一道hihocoder的編程題

題目如下

時(shí)間限制:20000ms
單點(diǎn)時(shí)限:1000ms
內(nèi)存限制:256MB

描述

有n個(gè)怪物，第i個(gè)怪物的血量是ai，設(shè)這n個(gè)怪物組成的集合為T。

現(xiàn)在你有一個(gè)技能，發(fā)動(dòng)一次需要花費(fèi)一個(gè)金幣，當(dāng)技能發(fā)動(dòng)后，所有存活的怪物的血量都會(huì)-1，當(dāng)怪物血量降為0后視為被消滅。

特別的，如果這次發(fā)動(dòng)的技能后有至少一只怪物死亡，你都將獲得一個(gè)金幣的獎(jiǎng)勵(lì)。

令f(S)為消滅集合S中的怪物總共需要付出幾個(gè)金幣，即花費(fèi)的金幣數(shù)量減去獲得的獎(jiǎng)勵(lì)金幣數(shù)量。

求∑S?T f(S)，答案對(duì)109+7取模。
輸入

第一行一個(gè)正整數(shù)n。

第二行n個(gè)正整數(shù)ai，表示第i個(gè)怪物的血量。

1 ≤ n ≤ 105，1 ≤ ai ≤ 109
輸出

輸出一個(gè)非負(fù)整數(shù)，表示答案。
樣例輸入

2
1 2

樣例輸出

1

我理解的思路
付出的金幣數(shù)量=技能的發(fā)動(dòng)數(shù)量-獎(jiǎng)勵(lì)的金幣數(shù)量。
技能的發(fā)動(dòng)數(shù)量為：生命值最高的怪的生命值。
獎(jiǎng)勵(lì)的金幣數(shù)量為：不同的生命值數(shù)量。
令g(S)表示集合S的生命值的最大值，h(S)表示集合S中不同生命值的數(shù)量，則f(S)=g(S)-h(S)。

我的疑惑
一個(gè)具體集合的金幣數(shù)量的計(jì)算很簡(jiǎn)單，但是如何高效的枚舉每個(gè)集合（每個(gè)集合怪物的最大生命值，以及小于最大生命值的怪物的構(gòu)成）,并且進(jìn)行計(jì)算

clipboard.png

clipboard.png
這張圖片的第二點(diǎn)和第三點(diǎn)不太理解

最后我希望有具體可行的代碼可以參考
附上題目鏈接鏈接

回答
編輯回答
扯機(jī)薄

就是普通的排列組合，別想多了。

  • 第二點(diǎn)：最大生命值為$w$，那么

    • $x$個(gè)生命值為$w$的里面至少要選一個(gè)：$2^x-1$
    • $y$個(gè)生命值小于$w$的有沒(méi)有都行：$2^y$

  • 第三點(diǎn)：包含生命值$w$，那么

    • $n-y$個(gè)生命值大于$w$的有沒(méi)有都行：$2^{n-y}$
    • $y$個(gè)生命值小于$w$的有沒(méi)有都行：$2^y$

至于它為什么$2^y$都要減$1$，想了一下，覺(jué)得意義不明。倒是$2^x$不減$1$肯定有問(wèn)題。

2018年4月18日 11:18
編輯回答
苦妄

把a(bǔ)1~an 按生命值分類 排序 得到k個(gè)集合 b1~bk
g(s)的和等于

gs = 0 
for bi in list<b> 
    w = b集合的生命值
    count = (2^len(bi)-1)*2^len(b1,...bi-1)
    // count代表最大生命值為w的所有集合的數(shù)量, 其中每個(gè)集合都需要 w 個(gè)金幣
    gs += w * count

h(s)的和等于

hs = 0
for bi in list<b>
    w = b集合的生命值
    count = (2^len(bi)-1)*2^(len(b1,...bi-1)+len(bi+1,...bk))
    // count代表所有集合里包含生命值為w的集合的數(shù)量, 其中每個(gè)集合都會(huì)在殺死w時(shí)都會(huì)獎(jiǎng)勵(lì) 1 個(gè)金幣
    hs += count
2018年9月8日 00:55