Last active
June 6, 2019 20:08
-
-
Save geoangelotti/f83b56ed640726d0a48770c74cbb9cbe to your computer and use it in GitHub Desktop.
ECE NTUA Computer Languages (Γλώσσες Προγραμματισμού) skitrip Greedy Algorithm.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdlib.h> | |
#include <stdio.h> | |
//Structure to save Height and Position of each station | |
struct station_struct { | |
long height; | |
long position; | |
}; | |
//Quicksort comparator | |
int tzompare(const void *a, const void *b) { | |
struct station_struct *pa = (struct station_struct *) a; | |
struct station_struct *pb = (struct station_struct *) b; | |
if (pa->height == pb->height) | |
//Height[a] == Height[b] so a < b if Position[a] < Position[b] else a > b | |
return (pa->position - pb->position); | |
else | |
//a < b if Height[a] < Height[b] else a > b | |
return (pa->height - pb->height); | |
} | |
int main(int argc, char **argv) { | |
//check if given input file | |
if (argc < 2) { | |
printf("Usage ./skitrip <in>\n"); | |
exit(1); | |
} | |
//open input file as readonly (fails otherwise) | |
FILE *fp; | |
fp = fopen(argv[1], "r"); | |
if (fp == NULL) { | |
printf("Null pointer did not open file successfully\n"); | |
exit(1); | |
} | |
//read first number => number of stations | |
long nstations; | |
if (fscanf(fp, "%ld\n", &nstations) < 1) { | |
printf("Not a number\n"); | |
fclose(fp); | |
exit(1); | |
} | |
//create a pointer of type station_struct and allocate memory | |
struct station_struct *stations; | |
stations = malloc(sizeof(struct station_struct) * nstations); | |
//read each following number and store the height and the position of each station | |
for (long i = 0; i < nstations; i++) { | |
if (fscanf(fp, "%ld\n", &stations[i].height) < 1) { | |
printf("Not a number\n"); | |
fclose(fp); | |
exit(1); | |
} | |
stations[i].position = i + 1; | |
} | |
fclose(fp); | |
//sort stations array ascending with Quicksort O(nlogn) | |
qsort(stations, nstations, sizeof(struct station_struct), tzompare); | |
long endpoint, d; | |
//endpoint of skitrip is the lowest station initially | |
endpoint = stations[0].position; | |
//distance of skitrip is 0 if Katerina descends at the lowest station | |
d = 0; | |
//traverse the array starting from the lowest station to the heightest | |
for (long i = 0; i < nstations; i++) { | |
//endpoint can be placed further back | |
if (endpoint > stations[i].position) | |
endpoint = stations[i].position; | |
//greedy approach to maximise the distance | |
if (d < stations[i].position - endpoint) | |
d = stations[i].position - endpoint; | |
} | |
//print out the distance | |
fprintf(stdout, "%ld", d); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment