Cultural Events (ois_events)

Aiuto
1

Non riesco a trovare l’errore nel codice, aldilà del tempo di esecuzione alcuni testcase danno sbagliati, se qualcuno può illuminarmi ne sarei grato. Il codice:

#include <stdio.h>
#include <assert.h>
#include <vector>
#include <algorithm>

#define MAXN 50000

using namespace std;

int N, V, i, k=0, ris;
int prices[MAXN], vouchers[MAXN];
vector<int> pr;
vector<int> vo;

int main() {
  freopen("input0.txt", "r", stdin);
  freopen("output0.txt", "w", stdout);

    assert(2 == scanf("%d %d", &N, &V));
    for(i=0; i<N; i++)
    {
        assert(1 == scanf("%d", &prices[i]));
        pr.push_back(prices[i]);
    }

    for(i=0; i<V; i++)
    {
        assert(1 == scanf("%d", &vouchers[i]));
        vo.push_back(vouchers[i]);
    }

    sort(pr.begin(), pr.end());
    sort(vo.begin(), vo.end());

    while((pr.size()!=0)&&(vo.size()!=0))
    {
        if(pr[0]<=vo[0])
        {
            vo.erase(vo.begin());
            pr.erase(pr.begin());
            ris++;
        }
        else if(pr[0]>vo[0])
        {
            pr.erase(pr.begin());
        }
    }

    printf("%d\n", ris);
    return 0;
}

Prima di tutto ordino i vettori, in caso l’evento possa essere comprato dal ticket elimino tutti e due e aggiorno il risultato, in caso contrario elimino l’evento in quanto, essendo i vettori ordinati ed esaminando il ticket con più valore, l’evento risulta troppo costoso per qualsiasi ticket; tutto ciò finchè uno dei due vettori risulta vuoto.

2

Se fai l’erase del primo elemento di pr pr[0] sarà sempre maggiore di vo[0] (l’ordinamento è crescente)

1 Mi Piace
3

Per fixare il tempo ti suggerisco di non fare l’erase, essendo in O(N).
Spero di aver risolto :slightly_smiling_face:

4

Totale dimenticanza del fatto che sort funziona in modo ascendente, grazie mille. Per l’erase come mi consigli di migliorarlo?
EDIT:
Risolto operando dall’altra “sponda” del vettore, il codice se interessasse a qualcuno:

#include <stdio.h>
#include <assert.h>
#include <vector>
#include <algorithm>

#define MAXN 50000

using namespace std;

int N, V, i, k=0, ris;
int prices[MAXN], vouchers[MAXN];
vector<int> pr;
vector<int> vo;

int main() {
//  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);

    assert(2 == scanf("%d %d", &N, &V));
    for(i=0; i<N; i++)
    {
        assert(1 == scanf("%d", &prices[i]));
        pr.push_back(prices[i]);
    }

    for(i=0; i<V; i++)
    {
        assert(1 == scanf("%d", &vouchers[i]));
        vo.push_back(vouchers[i]);
    }

    sort(pr.begin(), pr.end());
    sort(vo.begin(), vo.end());

    while((pr.size()!=0)&&(vo.size()!=0))
    {
        if(pr[pr.size()-1]<=vo[vo.size()-1])
        {
            vo.pop_back();
            pr.pop_back();
            ris++;
        }
        else
        {
            pr.pop_back();
        }
    }

    printf("%d\n", ris);
    return 0;
}
1 Mi Piace
5

Puoi invece di eliminare gli elementi tenerti i 2 indici ed incrementare quelli invece di riferirti sempre al primo elemento.