Programozás‎ > ‎Feladatok‎ > ‎Vasúti menetrend‎ > ‎Megoldás‎ > ‎

og_vonat.cpp

Letöltés: og_vonat.cpp

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
 
using namespace std;
 
 
struct menetrend
{
    int mik,med;
    char hon;
};
 
menetrend** a;
 
void beolvas(char*);
bool compare(menetrend, menetrend);
void docase(int);
void kiir(char*);
 
int n;
int* t;
int *na;
int *nb;
char c;
int* ki1;
int* ki2;
 
int main()
{
    beolvas("tt-large.in");
 
    ki1= new int[n];
    ki2= new int[n];
    for(int i=0; i<n; i++)
    {
        docase(i);
    }
 
    kiir("kimenet.out");
    return 0;
}
 
 
void beolvas(char* file)
{
    FILE* be = fopen(file, "r");
    fscanf(be, "%d", &n);
    a = new menetrend*[n+1];
    t = new int[n+1];
    na = new int[n+1];
    nb = new int[n+1];
    for(int i=0; i<n; i++)
    {
        fscanf(be, "%d", &t[i]);
        t[i]=t[i];
        fscanf(be, "%d %d", &na[i], &nb[i]);
        a[i]= new menetrend[na[i]+nb[i]+1];
        for(int j=0; j<na[i]; j++)
        {
            int temp1, temp2, temp3, temp4;
            fscanf(be, "%d%c%d", &temp1, &c, &temp2);
            fscanf(be, "%d%c%d", &temp3, &c, &temp4);
            a[i][j].hon='A';
            a[i][j].mik=60*temp1+temp2;
            a[i][j].med=60*temp3+temp4;
        }
        for(int j=0; j<nb[i]; j++)
        {
            int temp1, temp2, temp3, temp4;
            fscanf(be, "%d%c%d", &temp1, &c, &temp2);
            fscanf(be, "%d%c%d", &temp3, &c, &temp4);
            a[i][na[i]+j].hon='B';
            a[i][na[i]+j].mik=60*temp1+temp2;
            a[i][na[i]+j].med=60*temp3+temp4;
        }
    }
    fclose(be);
    return;
}
 
bool compare(menetrend x, menetrend y)
{
 
    if(x.mik>=y.mik) return false;
    return true;
}
 
 
void docase(int i)
{
    sort(a[i], a[i]+na[i]+nb[i], compare);
 
    int A=0; int B=0;
    priority_queue<int, vector<int>, greater<int> > Aq;
    priority_queue<int, vector<int>, greater<int> > Bq;
    Aq.push(32000);
    Bq.push(32000);
 
    for(int j=0; j<na[i]+nb[i]; j++)
    {
        if(a[i][j].hon=='A')
        {
            if(Aq.top()>a[i][j].mik)
            {
                A++;
                Bq.push(a[i][j].med+t[i]);
            }
            else
            {
                Aq.pop();
                Bq.push(a[i][j].med+t[i]);
            }
        }
        else if (a[i][j].hon=='B')
        {
            if(Bq.top()>a[i][j].mik)
            {
                B++;
                Aq.push(a[i][j].med+t[i]);
            }
            else
            {
                Bq.pop();
                Aq.push(a[i][j].med+t[i]);
            }
        }
        else
        {
            cout << "ERROR!!!!!";
            break;
        }
 
 
    }
    ki1[i]=A;
    ki2[i]=B;
    return;
}
 
 
void kiir(char* file)
{
    FILE* ki = fopen(file, "w");
    for(int i=0; i<n; i++)
    {
        fprintf(ki,"Case #%d: %d %d\n",i+1,ki1[i],ki2[i]);
    }
    fclose(ki);
    return;
}