I need to build a football team. Every player has his performance described by an integer. The greater the number, the more effective the player is. Every team should be solid. If one of the players plays much better than all others, then other team members will dislike him, and the team will not be solid. Thus, the performance of every team member should not exceed the sum of performances of any two other team members. Your task is to assemble a solid team with maximum total performance (which is the sum of performances of all players).
The first line of the input contains the number n (1 <= n <= 100000). The second line contains the performances of every of the n players. Performances are positive integers not greater than 2^31.
The output should contain two lines. The first line should contain the maximum total performance of the team you can build from given players. The second line should contain the numbers of the players (in ascending order) that you need to put to your team in order to reach this performance. The players have numbers starting from 1 to n in the same order that their performances appear in the input. If there are several ways to build the team, output any of them.
For example:
Input:
5
3 2 5 4 1
Output:
14
1 2 3 4
I have invented such algorithm:
Read all numbers from input.
Sort them in ascending by recursive qicksort.
Iterate through sorted vector and accumulate two sums, choosing the maximum of them and keeping indexes of the begining and the end of two optimal sequences.
Here is my code for this algorithm:
#include <iostream>
#include <fstream>
#include <vector>
#include <stdlib.h>
#include <time.h>
#include <algorithm>
using std::swap;
using std::vector;
using std::cout;
using std::cin;
typedef unsigned long ulong;
typedef unsigned long long ullong;
template <typename T>
int random_partition(vector<T> &input, int start, int end)
{
srand(time(NULL));
int pivotIdx = start + rand() % (end - start + 1);
T pivot = input[pivotIdx];
swap(input[pivotIdx], input[end]);
pivotIdx = end;
int ind = start - 1;
for (int j = start; j <= end - 1; ++j)
{
if (input[j] <= pivot)
{
ind = ind + 1;
swap(input[ind], input[j]);
}
}
swap(input[ind + 1], input[pivotIdx]);
return ind + 1;
}
template <typename T>
void random_quick_sort(vector<T>& input, int start, int end)
{
if (start < end)
{
int mid = random_partition(input, start, end);
random_quick_sort(input, start, mid-1);
random_quick_sort(input, mid + 1, end);
}
}
struct Player
{
int number;
ulong efficiency;
Player(int numb, ulong ef) : number(numb), efficiency(ef) {}
};
bool operator <= (const Player& plRight, const Player& plLeft)
{
return (plRight.efficiency <= plLeft.efficiency);
}
class Team
{
vector<Player> players;
vector<int> bestPlayersNumbers;
ullong sumOfBestPlayers;
public:
Team() {}
void addPlayer(Player player)
{
players.push_back(player);
}
void sortPlayersByEfficiency()
{
random_quick_sort(players, 0, players.size() - 1);
}
void choosePlayers()
{
sortPlayersByEfficiency();
int subListBegin = 0;
int prevSubListBegin = 0;
int subListEnd = 1;
int prevSubListEnd = 0;
ullong currentMaxSum = 0;
if (players.size() < 2)
{
currentMaxSum = players[0].efficiency;
}
else
{
currentMaxSum = players[0].efficiency + players[1].efficiency;
prevSubListEnd = 1;
}
ullong prevMaxSum = currentMaxSum;
for (int iter = 2; iter < players.size(); ++iter)
{
while (players[iter].efficiency - players[subListBegin].efficiency >
players[subListBegin + 1].efficiency )
{
currentMaxSum = currentMaxSum - players[subListBegin].efficiency;
++subListBegin;
}
currentMaxSum += players[iter].efficiency;
subListEnd = iter;
if ( prevMaxSum <= currentMaxSum)
{
prevMaxSum = currentMaxSum;
prevSubListEnd = subListEnd;
prevSubListBegin = subListBegin;
}
}
sumOfBestPlayers = prevMaxSum;
for (int i = prevSubListBegin; i <= prevSubListEnd; ++i)
{
bestPlayersNumbers.push_back(players[i].number);
}
random_quick_sort(bestPlayersNumbers, 0, bestPlayersNumbers.size() - 1);
}
void printSumAndPlayers()
{
printf("%ull\n", sumOfBestPlayers);
for (int i = 0; i < bestPlayersNumbers.size(); ++i)
{
printf("%i ", bestPlayersNumbers[i] + 1);
}
}
};
int main()
{
clock_t begin, end;
double time_spent;
FILE *file;
file = fopen("test.txt", "r");
int playersNumber;
Team team;
fscanf(file, "%i", &playersNumber);
for (int i = 0; i < playersNumber; ++i)
{
ulong playerEffeciency = 0;
fscanf(file, "%ul", &playerEffeciency);
team.addPlayer(Player(i, playerEffeciency));
}
begin = clock();
team.choosePlayers();
team.printSumAndPlayers();
end = clock();
time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
std::cout << time_spent << std::endl;
return 0;
}
This algorithm works correctly, but it is rather slow. I need it to work faster, but I can't work out something more effective at the moment. Can you give me some ideas how I can optimize my algorithm to make it work faster?
I will be grateful for your help.
randomPartition()
only used for returning anint
, or is the modified vector used after the call? If the latter, then you may benefit from passinginput
byconst&
and working on a local copy. \$\endgroup\$