A programming problem of hihocoder

the topics are as follows

time limit: 20000ms
single point time limit: 1000ms
memory limit: 256MB

description

there are n monsters, and the health of the I monster is set to T by ai,.

now you have a skill that costs one gold coin to start each time. When the ability is started, the health of all living monsters will be-1. When the health of the monster is reduced to 0, it is considered to be destroyed.

In particular, if at least one monster dies after this ability, you will be rewarded with a gold coin.

causes f (S) to pay a total of several gold coins to destroy the monsters in set S, that is, the number of gold coins spent minus the number of reward coins received.

to find the answer of S T f (S), take the model 109-7.
enter

the first line is a positive integer n.

the second row of n positive integers ai, represents the amount of blood of the I th monster.

1 n 105 ai
output

outputs a non-negative integer to represent the answer.
sample input 

2
1 2

sample output 

1
< hr >

the way of thinking I understand
the number of gold coins paid = the number of skills initiated-the number of gold coins rewarded. The number of launches for the
ability is: the weird health with the highest health.
the number of gold coins rewarded is: the number of different health points.
Let g (S) represent the maximum health of set S, h (S) represents the number of different health values in set S, then f (S) = g (S)-h (S).

my doubts
the calculation of the number of gold coins in a specific collection is very simple, but how to efficiently enumerate each collection (the maximum health value of each collection monster, and the composition of monsters less than the maximum health value), and calculate

clipboard.png

clipboard.png
the second and third points of this picture do not quite understand

Finally, I hope to have specific and feasible code to refer to
attach the topic link link

Programming algorithm acm
Apr.20,2021

is a common arrangement and combination, so don't think too much about it.

  • second point: if the maximum health value is $wicked, then

    • $x$ at least one of the health values of $w$ should be chosen: $2 ^ x-1 $
    • $y$ all have health values less than $w$: $2 ^ y $

  • third point: if the value of life is $wicked, then

    • $nmury$ anyone with a health value greater than $w$ is fine: $2 ^ {nmury} $
    • $y$ all have health values less than $w$: $2 ^ y $

as to why $2 ^ y $should be reduced by $1 million, I thought for a moment and found that the meaning was unclear. But there must be something wrong with $2 ^ x $not minus $1 $.

the sum of k sets b1~bk
g (s) is equal to

by sorting a1~an by life value. 
gs = 0 
for bi in list<b> 
    w = b
    count = (2^len(bi)-1)*2^len(b1,...bi-1)
    // countw,  w 
    gs += w * count
The sum of

h (s) equals 

hs = 0
for bi in list<b>
    w = b
    count = (2^len(bi)-1)*2^(len(b1,...bi-1)+len(bi+1,...bk))
    // countw, w 1 
    hs += count

Previous: Please tell me how to judge the code of NODEJS.

Next: Centos7 crontab does not execute?

css mysql arrays josn react html typescript webpack npm sass R objective-c .net sql-server jquery python-3.x angularjs django angular excel regex iphone ajax linux xml pandas vba spring database wordpress string wpf xcode windows bash postgresql oracle multithreading eclipse list firebase algorithm macos forms image scala visual-studio azure bootstrap spring-boot react-native python-2.7 docker performance function winforms matlab powershell apache dataframe api sqlite numpy rest shell selenium flutter dart maven loops qt swing android-studio csv express file class tensorflow sorting codeigniter perl
© 2021 CodesHelper
Advertising Contact us About us
Menu