Come risolvere questo problema di posti a sedere?

Question

Come risolvere questo problema di posti a sedere?

#1 da (7 voti)

0

Stavo risolvendo un problema di posti a sedere la cui soluzione sembra banale ma non riesco a ottenerla. In breve, il problema è che dobbiamo collocare n (pari) studenti in n / 2 righe in cui gli studenti sono etichettati da 1 a n e non due studenti adiacenti dovrebbero avere etichette consecutive come "1 2" o "5 4". Inoltre, ogni studente è in classe L o R. Nessuna riga dovrebbe avere studenti R nella posizione sinistra e L studente nella posizione giusta contemporaneamente.

Il mio approccio era scegliere prima uno studente da una classe non vuota e poi scorrere tutti gli altri studenti di sinistra in modo che fosse possibile sedersi con lui e farli sedere e così via. In questo processo scelgo prima dalla classe L e lo metto a sinistra e se è vuoto, allora dalla classe R.

Qui:

        List<Integer> L = new ArrayList<>();
        List<Integer> R = new ArrayList<>();
        int n = in.nextInt();//number of students
        String s = in.nextLine();//It is a string like "RRLRLRLL" where i^th character is the class of i^th student
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == 'L')
                L.add(i + 1);
            else
                R.add(i + 1);
        }
        for (int i = 0; i < n / 2; i++) {
            int x = (L.size() > 0) ? L.remove(0) : R.remove(0);
            int y = 0;
            if (L.size() > 0) {
                y = findfrom(x, L, R);
            } else if (R.size() > 0) {
                y = findfrom(x, R, L);
            }
            out.println(x + " " + y);

private int findfrom(int x, List<Integer> L, List<Integer> R) {
    int y = -1;
    int j = 0;
    do {
        y = L.get(j);
        j++;
    } while (Math.abs(y - x) == 1 && j < L.size());
    if (Math.abs(y - x) != 1)
        L.remove(new Integer(y));
    else
        y = findfrom(x, R, L);
    return y;
}

Ma questo fallirebbe nel caso in cui n = 6 e L = [2,3,6] e R = [1,4,5] (RLLRRL). Ora sceglieremo 2 e 6. Poi 3 e 1. Poi a sinistra ci sono 4 e 5, che è un problema.

Ho anche pensato di fare: - DFS - Accordo casuale seguito dallo scambio dello studente sbagliato con un'altra posizione possibile

Che cosa posso fare, cosa non sto pensando?

^{Vedi "Problem-234A: Codeforces" per ulteriori dettagli.}

java algorithms

posta RE60K 07.07.2016 - 07:12

fonte

1 risposta

Leggi altre domande sui tag java algorithms

Come ottenere una buona panoramica di un backlog Agile? Secondo Clean Code, va bene aggiungere un singolo costruttore a una semplice struttura dati?

score 7 · Accepted Answer

Il problema ti sta invitando a pensarlo troppo. Puoi risolverlo assicurandoti di non dare ad ogni regola più potere su di te di quanto meriti. Questo è un problema di raccolta dei requisiti. Bollire sempre un requisito fino ai reali bisogni. Non lasciare che crei ulteriori presupposti su ciò di cui ha bisogno.

Quello che ti manca è che la parte RL del problema (gomito) è di facile soluzione.

Uno degli output di esempio ha il seguente aspetto:

1 4
2 5
6 3

Ciò significa che 1 e 2 non sono considerati adiacenti l'uno all'altro. Quindi essere adiacenti avviene solo orizzontalmente, cioè alla stessa scrivania.

Questo rende il problema RL banale perché non importa quale scrivania si trovi accanto a quale scrivania. Hai solo bisogno di coppie i cui numeri non siano in conflitto. Una volta che hai puoi correggere RL semplicemente scambiandoli perché LR è legale come LL e RR.

Posso persino prevedere come otterranno sempre il loro risultato. Il loro metodo per trovare coppie non in conflitto è quello di tagliare il gruppo a metà per creare due gruppi e abbinare il più basso al più alto.

È ovvio se pensi a questo:

6  
LLRLLL

come

L R  
===
1  
2  
  3  
---
4  
5  
6

L'associazione dal primo all'ultimo dà l'output di esempio. Anche in questo caso:

1 4
2 5
6 3

La manualità è simile a:

L L
L L
L R

Potresti averlo fatto anche

L L
L L
R L

con

1 4
2 5
3 6

Ma ciò provoca il gomito del gomito.

Accoppiare il primo semestre con il secondo tempo per non accoppiare i numeri in conflitto insieme a meno che n = 2. Che va bene perché se n = 2 il problema non è comunque risolvibile.

Una soluzione di pseudo codice:

Students 1 to n/2, please sit at the desk that matches your student number. Of the two seats at that desk choose the one that keeps your elbow from poking your partner.

Students n/2+1 to n, please sit in the remaining chair at the desk that is n/2 less than your student number.

Fatto in questo modo non è nemmeno necessario scambiare.

Questa soluzione non è venuta solo a me. All'inizio pensavo al backtracking, alla ricerca della profondità, al ragionamento basato su regole. Poi ho pensato, aspetta, inizia semplice e fai che il problema dimostri che è complicato. Vediamo come appare se visualizzo il problema nel testo. Ho iniziato a digitare numeri in ordini diversi, prima riga, prima colonna. Ho provato a far scorrere la colonna. Mi è venuta l'idea di mostrare la manualità dei numeri creando colonne L e R quindi non ho dovuto continuare a guardare LLRLLL per vedere quale era. Dopo che tutto è andato a posto. Un'occhiata all'output di esempio mi ha detto esattamente cosa avevano fatto. Tutto perché avevo creato un modo utile per esprimere l'input che semplificava la risoluzione del problema.