algorithm - Distribution strategy to minimize the maximum value in an array -

-

recently, come across problem in solving problem. have solution myself. i'm not quite satisfied time complexity. so, i'm turning guys possible better solution. problem follows:

suppose there integer array int arr[n]. have integer value val in hand distribute arr. example, can increase arr[0] val, or arr[2] 1 , arr[3] val - 1, , on. goal minimize maximum value in arr after distribution. there may multiple solutions, , do.

my current solution follows. it's trivial , takes o(val) time. have feeling better solution exists.

for (int = 0; < val; ++i) {   // increase minimum value in arr 1 }

here's linear-time algorithm. first try increase current max. if have keep going, distribute rest evenly possible. in untested python:

def distribute(arr, val):     maxarr = max(arr)     x in arr:         val -= min(maxarr - x, val)     return maxarr - (-val) // len(arr)

the double minus silliness ceiling division.


Comments

Post a Comment

Popular posts from this blog

c# - How Configure Devart dotConnect for SQLite Code First? -

-
can configure following sample code ? when run following code, error : no entity framework provider found ado.net provider invariant name 'devart.data.sqlite' setting in machine.config <system.data> <dbproviderfactories> <add name="dotconnect sqlite" invariant="devart.data.sqlite" description="devart dotconnect sqlite" type="devart.data.sqlite.sqliteproviderfactory, devart.data.sqlite, version=4.6.287.0, culture=neutral, publickeytoken=09af7300eec23701" /> </dbproviderfactories> </system.data> after add below block code in app.config <?xml version="1.0"?> <configuration>   <configsections> <!-- more information on entity framework configuration, visit http://go.microsoft.com/fwlink/?linkid=237468 --> <section name="entityframework" type="system.data.entity.internal.configfile.entityframeworksection, entit...
Read more

erlang - Saving a digraph to mnesia is hindered because of its side-effects -

-
updated the digraph library in erlang implements data type side-effectful. each operation on data type saves new state in ets table -- instead of returning altered version of itself, more common in functional languages. the problem usage perspective, impedes effort store or pass around state in convenient way requiring me first "collect" state before can start juggle around. the closest solution have seen far serializer/deserializer , these have drawback tied current structure of digraphs instead of operating on abstract type -- prevents future proof solution. update pascal pointed out serializer utilizes interface of digraph, , hence eliminates drawback mentioned above. better, albeit still inconvenient, see no better alternative. what recommendation on how store digraphs? should go different data type altogether? thanks. i not sure understand concern. fact digraph stored in ets transparent in user interface, might want chnge either exchange digr...
Read more

java - Copying object fields -

-
what best way of copying classes when need have 2 independent variables? have simple class: public class myclass { boolean = false; string b= "not empty"; } do need make method : assign(myclass data ) { a= data.a; b= data.b; } is there automatic method copy (duplicate) objects in java? do need make method : pretty close. instead of making method, should make constructor. such constructors called copy constructor , , create them this: myclass(myclass data) { = data.a; b = data.b; } and create copy of instance, use constructor this: myclass obj1 = new myclass(); myclass obj2 = new myclass(obj1); copy constructor can tedious : using copy constructor create deep-copy can tedious, when class has mutable fields. in case, assignment create copy of reference, , not object itself. have create copy of fields (if want deep copy). can go recursive. a better way create deep copy serialize , deserialize object. why not use clone()? ...
Read more