一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1010|回复: 4
收起左侧

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

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

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

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

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 | 显示全部楼层
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 04:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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