algorithm - Find minimum time required to collect C gifts from A machines given access to B bags? -

-

I have an interview next week and I am practicing problems for the same. I came to this question, can you please solve it?

A gift vending machine and you have to collect b sachet / strong> gifts. Each gift vending machine has unlimited gifts.

Each machine started leaving gifts at the time C and left the gift every Ii seconds. You can arrange pouch in any way, but once they are set below a machine, you can not take it on any other machine. You need to collect the gifts in the shortest possible time.

Input

The first line contains integers A, B, C.

The integer in the second row, C (different from one space), I go from 1 to A.

In the third line, integers Ii (different from one space), I go from 1 to A.

Output

An integer that calculates the minimum time

I think the method was very incompatible. I thought that all of us can equate the subsets of all to the equivalent of their cardinal number B. And then select the one that gives the minimum time .

This approach seems to be brute force, so I'm looking for another alternative approach.

Can any of you help me with it?

first write a function 

  int max_num_gifts (A, B , T, S [], L [])   
 which you can calculate the maximum number of gifts  t   can be done in time:  S []  and  l []  number of gifts machine  A [ I]  drops is  (ts [i]) / l [i] + 1 . Then the top  B  machines that leave the most gifts. See on how to select  O (n)  in time.  
 Then you can only loop through time  t = 1,2, ...  until  max_num_gifts & gt; = C  Or better still, you can use a binary search to search such a  t : Start with  t = 1  Then  t = 2 ,  T = 4 ,  t = 8  etc. Unless you receive a large number, then the required  t Binary search for .  
 Complexity of overall time should be  O (A * lg (T_min)) .

Comments

Post a Comment

Popular posts from this blog

php - PDO bindParam() fatal error -

-
I am trying to learn PDO, now I have written this small code, but it gives me a serious error: < P> Fatal error: Call a member function at a non-object dot () ... $ con = new mysqli ("127.0.0.1", "root", "", "csvdangercheck"); $ Query = $ con- & gt; ("Id,` var1`, `var2`) values ​​(" id,: var1,: var2) ";); $ query- & gt; bypass pattern (': id', $ id); $ query- & gt; BindParam (': var1', $ VAL1); $ Query- & gt; bindParam (': var2', $ val2); $ Query-> Executed (); I Trying to use print_r ($ con-> errorInfo ()) but Fatal error: Undefined method mysqli :: errorInfo ( ) ... can someone tell me what am I missing? Flaffeh said, you have PDO Missing Mysqy, try it: $ con = new PDO ('mysql: host = 127.0.0.1; dbname = csvdangercheck', 'root', '');
Read more

logging - How can I log both the Request.InputStream and Response.OutputStream traffic in my ASP.NET MVC3 Application for specific Actions? -

-
For a specific set of tasks, I need to log in to the incoming request inputstream as well as outgoing response. is. I am using an ActionFilterAttribute for this and overriding the OnActionExecuted and OnResultExecuted methods. So I'm starting with this idea ... Public category ActionLoggerAttribute: ActionFilterArrbit {Public Override Zero On-Offed Execution (ActionActioned Contact Filter Filter) {base.OnActionAxecuted (FilterContext); HttpRequestBase request = filterContext.HttpContext.Request; // TODO: Log the request. InputStream} Public Override Zero OnResultExecuted (ResultExecutedContext FilterContext) {base.OnResultExecuted (filterContext); HTTPRPSPointBase Response = FilterContacts Hpptex response; // TODO: Log on Response.OutputStream}} Ideally I'll hook it up with enterprise library logging because I'm already using it for error logging. Am I reaching the input and output stream at the right time? Can I easily use the Enterprise Library to log i
Read more

java - Why my included JSP file won't get processed correctly? -

-
I am trying to create Java web framework (and learning), and on the basis of 'Code Generator In the process of making the material view of the database in the process of development, I stumbled into a difficulty, which I do not know how to solve it. First of all, I want the following index.jsp : & lt; Body & gt; Use all pages to be created. & Lt;% @ include file = "header.jsp"% & gt; & Lt; Hours / & gt; & Lt;% @ included file = "body.jsp"%> & Lt; Hours / & gt; & Lt;% @ include file = "footer.jsp"% & gt; & Lt; / Body & gt; And, in body.jsp , I should have it like this: & lt; Jsp: include page = "$ {Application_modul}"%> Where application_modul is an attribute defined in its controller: request.setAttribute ("application_modul", "USER_ACCOUNT \\ ' View_user_account.jsp "); This file can be found properly, but the processed JSP does
Read more