Per la sfida seguente da un sito di programmazione, sono un po 'confuso.
Dichiarazione di problemi:
Un professore di fisica ha dato progetti agli studenti della sua classe. Gli studenti devono formare una squadra di due persone per fare il progetto. Il professore ha lasciato gli studenti per decidere le squadre. Il numero di studenti in una classe sarà pari.
Ogni studente ha un livello di conoscenza. Racconta quante conoscenze ha ogni studente. Il livello di conoscenza di una squadra è la somma dei livelli di conoscenza di entrambi gli studenti.
Gli studenti decidono di formare gruppi in modo tale che la differenza tra la squadra con la conoscenza più alta e quella con la conoscenza minima sia minima.
ingresso
La prima riga dell'input conterrà il numero di casi di test t; Nelle successive righe t il primo numero è n il numero di studenti nella classe seguito da n interi che denotano i livelli di conoscenza degli studenti n
Output
Il tuo output dovrebbe essere una singola riga contenente la minima differenza possibile tra la squadra con la conoscenza più alta e quella con la conoscenza più bassa.
Input di esempio
2
4 2 6 4 3
6 1 1 1 1 1 1
Output di esempio
1
0
[My Attmept]
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ProjectTeam
{
class Program
{
static void Main(string[] args)
{
int testCasesCount = Convert.ToInt32(Console.ReadLine());
// Solve each test case
for (int i = 0; i < testCasesCount; i++)
{
String line = Console.ReadLine();
String[] components = line.Split(' ');
int numberOfStudents = Convert.ToInt32(components[0]);
int[] studentsKnowledge = new int[numberOfStudents];
// Read input
for (int j = 0; j < numberOfStudents; j++)
{
studentsKnowledge[j] = Convert.ToInt32(components[j + 1]);
}
// Done
// Solve
List<int> listOfPossibleTeams = new List<int>();
for (int k = 0; k < numberOfStudents; k+=2)
{
int knowledge = studentsKnowledge[k] + studentsKnowledge[k + 1];
// Create others
if (k >= 2)
{
int toPair = studentsKnowledge[k];
for (int l = k-1; l >= 0; l--)
{
listOfPossibleTeams.Add(toPair + studentsKnowledge[l]);
}
toPair = studentsKnowledge[k + 1];
for (int l = k-1; l >= 0; l--)
{
listOfPossibleTeams.Add(toPair + studentsKnowledge[l]);
}
}
//
listOfPossibleTeams.Add(knowledge);
}
listOfPossibleTeams.Sort();
// select minimum knowledge diff
int minumimKnowledge = int.MaxValue;
for (int m = 0; m <= listOfPossibleTeams.Count() - numberOfStudents / 2; m++)
{
int diff = Math.Abs(listOfPossibleTeams[m] - listOfPossibleTeams[m +(numberOfStudents / 2) - 1]);
if (diff < minumimKnowledge)
{
minumimKnowledge = diff;
}
}
Console.WriteLine(minumimKnowledge);
}
}
}
}
Ma la soluzione di cui sopra non riesce per il caso di test:
1
8 4 2 4 2 1 3 3 7
Il mio codice emette 0, mentre la risposta effettiva è 2.
Il mio approccio consiste nel creare tutte le possibili combinazioni valide di squadre, e ottenere le loro conoscenze, ordinare tutte le conoscenze e selezionare n / 2 (n è il numero di studenti) elementi contigui aventi una differenza minima tra i confini della selezione. Ma questo non funziona.
Alla fine ho trovato il problema risolto da qualcuno su Internet, e ho provato la soluzione e ha funzionato. Ma non capisco come funziona? Il codice seguente:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ProjectTeam
{
class Program
{
static void Main(string[] args)
{
int testCasesCount = Convert.ToInt32(Console.ReadLine());
// Solve each test case
for (int i = 0; i < testCasesCount; i++)
{
String line = Console.ReadLine();
String[] components = line.Split(' ');
int numberOfStudents = Convert.ToInt32(components[0]);
List<int> studentsKnowledge = new List<int>();
// Read input
for (int j = 0; j < numberOfStudents; j++)
{
studentsKnowledge.Add(Convert.ToInt32(components[j + 1]));
}
studentsKnowledge.Sort();
// Done
// Solve
int diff = (studentsKnowledge[0] + studentsKnowledge[numberOfStudents - 1]);
int max = diff, min = diff;
for (int k = 1; k < studentsKnowledge.Count / 2; k++)
{
diff = studentsKnowledge[k] + studentsKnowledge[numberOfStudents - 1 - k];
if (diff > max)
max = diff;
if (diff < min)
min = diff;
}
Console.WriteLine(max - min);
}
}
}
}
Non capisco come funziona il codice sopra. Il codice sopra non crea nemmeno tutte le possibili combinazioni. Sta usando un concetto matematico a cui non riesco a pensare, o la mia interpretazione del problema è sbagliata? Per favore aiuto.