《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 1276|回复: 4
收起左侧

[算法题] 请教一道HackeRrank的题

[复制链接] |试试Instant~ |关注本帖
monsterhunter 发表于 2015-5-2 01:30:54 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
Problem Statement

HackerRank is conducting a teamed programming contest. The rules of the contest are a bit different than usual:

A team consists of exactly N members.
Problemset contains exactly N problems and each team member must solve exactly 1 problem.
Only one member from the team is allowed to read the problem statements before the contest start time.
Note that not everyone have read the problems at first. So, to solve problems a member needs to know the statements from some teammate who already knows them. After knowing problems once, a member is eligible to explain them to other teammates ( one teammate at a time ). You can assume that the explaining ( 1 or N problems ) will always take D minutes. During explaining, none of the two involved members will be able to do anything else.

Problems are of different difficulty levels. You can assume that it will take Ti minutes to solve the ith problem, regardless of which member solves it.

Given a team's data, what is the minimum possible time in which they can solve all problems?

Input Format

The first line will contain T, the number of test cases.
The first line of each test case will contain space-separated integers N and D. The second line will contain N space-separated integers, where the ith integer denotes Ti.

Constraints

1≤T≤20
1≤N≤3×103
1≤Ti,D≤109
Output Format

For each test case, output the minimum possible time in which the given team will be able to solve all problems in a separate line.

Sample Input

1
2 100
1 2
Sample Output

102
Explanation

Member 1 is allowed to know problems before start time. He starts explaing problems to member 2 when contest starts. Explaining ends at the 100th minute. Then both of them immidiately starts solving problems parallely. Member 1 solved 1st problem at the 101th minute and member 2 solved 2nd problem at the 102th minute.
========================================================
我看到别人有个非常optimum的solution, 如下:

void solve(int test_num) {
  int N, D;
  cin >> N >> D;
  vector<int> take(N);
  for (int i = 0; i < N; i++)
    cin >> take;
  //sort(take.begin(), take.end());
  priority_queue<ll> pq;
  for (int i = 0; i < N; i++)
    pq.push(-take);
  while (pq.size() > 1) {
    const ll a = -pq.top();
    pq.pop();
    const ll b = -pq.top();
    pq.pop();
    pq.push(-(b + D));
  }
  cout << (-pq.top()) << endl;
}


请问哪位能够讲解一下思路么?
hitchpy 发表于 2015-5-2 10:10:47 | 显示全部楼层
我觉得想法大概是:
从小到大的在heap里面的都看成是一个“大问题”,或是一个问题集,按照递归,你已经知道知道这个组best case需要的时间,也就是code里面的a。因为到后面a可能就不是一个问题而是一个问题集。然后你和另外一个问题集,或者一个新问题b,因为b花时间更多,于是你就先用d时间把问题传给b,于是这个组需要一共d + b时间完成。大概就是这么个思路?
回复 支持 反对

使用道具 举报

 楼主| monsterhunter 发表于 2015-5-2 14:22:58 | 显示全部楼层
hitchpy 发表于 2015-5-2 10:10
我觉得想法大概是:
从小到大的在heap里面的都看成是一个“大问题”,或是一个问题集,按照递归,你已经知 ...

ok, 我大概懂了, 这道题很tricky, 因为正常想一定是从最长的时间开始算。
回复 支持 反对

使用道具 举报

王可雪 发表于 2015-5-3 23:02:39 | 显示全部楼层
题目名字是什么?
回复 支持 反对

使用道具 举报

 楼主| monsterhunter 发表于 2015-5-3 23:08:49 | 显示全部楼层
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-11-21 18:36

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表