Come selezionare i team con la differenza minima tra i livelli di conoscenza

-1

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.

    
posta user47487 13.03.2015 - 12:49
fonte

1 risposta

3

In questa risposta mi concentrerò sulla parte pensante e meno sulla parte di codifica. In altre parole, se il pensiero non è corretto, il codice probabilmente non darà il risultato che ti aspettavi, anche se il codice implementa fedelmente il tuo pensiero.

Indicherò semplicemente il difetto nella parte del codice, senza entrare nei dettagli: listOfPossibleTeams conteneva tutte le possibili somme di coppie, senza considerare i conflitti - se hai già abbinato gli studenti A e B, non è permesso abbinare nuovamente B e C perché ciò avrebbe assegnato B a due squadre contemporaneamente. Tuttavia, l'array listOfPossibleTeams conterrà le somme di A+B e B+C e A+C , e l'utilizzo successivo di questo array non ha provato a rilevare questo conflitto. Questo è il motivo per cui la risposta è sbagliata.

Le conoscenze matematiche necessarie per comprendere questo conflitto sono insegnate in Combinazioni

Capire perché la soluzione corretta funziona è un po 'più coinvolta. La conoscenza matematica è insegnata in Statistica ordini , ma in genere gli studenti che sono bravi in informatica sono in grado di inventare un'intuizione sulla statistica dell'ordine indipendentemente dal fatto che lo apprendano da scuola formalmente. (Solo opinione personale, nessun riferimento)

Un modo di pensare intuitivamente al problema è questo, tramite divide e conquista:

  1. Supponiamo che gli studenti siano divisi in due gruppi: la metà superiore e la metà inferiore.
  2. Diciamo che scegli due studenti della metà superiore (denominati A e B) e due studenti della metà inferiore (denominati C e D).
    • Sarebbe meglio se accoppiassimo i due dalla metà superiore (A con B), e poi accoppiasse i due dalla metà inferiore (C con D)?
    • Oppure, sarebbe meglio se ne accoppiassimo uno da ciascuna metà, dando (A con C) e (B con D)?
  3. Noterai che è sempre meglio accoppiarne uno dalla metà inferiore con uno dalla metà superiore (quest'ultimo caso).
  4. Ora, ulteriormente suddivisione in più livelli, e ripetere il test. Alla fine, vedrai intuitivamente che l'abbinamento tra il più alto e il più basso potrebbe essere una buona strategia che vale la pena provare.

Cercare di dimostrarlo con i teoremi richiederà molto più impegno. La maggior parte delle volte, un alunno che studia informatica proverà a fare un tentativo e vedrà se il codice fornisce le stesse risposte degli esempi funzionanti. In altre parole, non tutti passano attraverso il processo teorico quando cercano una soluzione. Alcuni vanno con intuito e sono stati in grado di affrontare i compiti, almeno a livello introduttivo.

    
risposta data 13.03.2015 - 13:42
fonte

Leggi altre domande sui tag