From 3a3843673d8401f224901ad170aaf2ab8c3b1f46 Mon Sep 17 00:00:00 2001
From: Nguyễn Gia Phong <vn.mcsinyx@gmail.com>
Date: Fri, 20 Jul 2018 15:04:12 +0700
Subject: Revise a few competive exersises

---
 12/QG-2014/minroad.c | 69 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 69 insertions(+)
 create mode 100644 12/QG-2014/minroad.c

(limited to '12/QG-2014/minroad.c')

diff --git a/12/QG-2014/minroad.c b/12/QG-2014/minroad.c
new file mode 100644
index 0000000..d4bc129
--- /dev/null
+++ b/12/QG-2014/minroad.c
@@ -0,0 +1,69 @@
+#include <stdlib.h>
+#include <stdio.h>
+
+struct trees {
+	long d, a, b;
+};
+
+int cmp(const void *x, const void *y)
+{
+	long d = ((struct trees *) x)->d - ((struct trees *) y)->d;
+	if (d < 0)
+		return -1;
+	else if (d > 0)
+		return 1;
+	else
+		return 0;
+}
+
+int main()
+{
+	FILE *f = fopen("MINROAD.INP", "r");
+	long n, a, b;
+	fscanf(f, "%ld %ld %ld\n", &n, &a, &b);
+
+	struct trees *t = (struct trees *) malloc(n * sizeof(struct trees));
+	long k;
+	for (long i = 0; i < n; i++) {
+		fscanf(f, "%ld %ld\n", &t[i].d, &k);
+		if (k == 1) {
+			t[i].a = 1;
+			t[i].b = 0;
+		} else {
+			t[i].a = 0;
+			t[i].b = 1;
+		}
+	}
+	fclose(f);
+
+	qsort(t, n, sizeof(struct trees), cmp);
+	for (long i = 1; i < n; i++) {
+		t[i].a += t[i - 1].a;
+		t[i].b += t[i - 1].b;
+	}
+
+	struct trees *enough = t;
+	for (k = n; k > 0 && (enough->a < a || enough->b < b); k--)
+		enough++;
+
+	long d0 = -1, d1, maxa, maxb;
+	for (; k--; enough++) {
+		maxa = enough->a - a;
+		maxb = enough->b - b;
+		while (t->a <= maxa && t->b <= maxb) {
+			t++;
+			n--;
+		}
+
+		d1 = d0;
+		d0 = enough->d - t->d;
+		if (d1 != -1 && d1 < d0)
+			d0 = d1;
+	}
+
+	f = fopen("MINROAD.OUT", "w");
+	fprintf(f, "%ld\n", d0);
+	fclose(f);
+
+	return 0;
+}
-- 
cgit 1.4.1