登录
  • #刷题

请教一道HackeRrank的题

monsterhunter
2100
4
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;

}

请问哪位能够讲解一下思路么?
4条回复
热度排序

发表回复