USACO Ordered Fractions

私の考え:すべての点数を列挙して、それが最も簡単かどうかを判断して(分母分子の最大公約数=1)、1つの数列ですべての最も簡単な点数を記録して、それから速い列で並べ替えます.

/*
ID: wangxin12
PROG: frac1
LANG: C++
*/

#include 
#include 
#include 
#include 
#include 

using namespace std;

class Fraction {
public:
	int numerator;
	int denominator;
};

int N;

int GCD(int a, int b) {
	//Euclidean Algo
	if(a < b) return GCD(b, a);

	if(b == 0) return a;
	else return GCD(b, a % b);

	/*
	int r = a % b;
	if(r == 0) return b;
	else return GCD(b ,r); 
	*/
}

vector result;

bool Cmp(Fraction & a, Fraction & b) {
	if( a.numerator * b.denominator >= a.denominator * b.numerator ) return true;
	else return false;
}

template
int Partition(vector & f, int start, int finish, bool (cmp)(T & a, T & b)) {
	T key = f[start];
	int left = start + 1;
	int right = finish;

	while(true) {
		
		while(right > left && cmp(f[right],key)) right--;
		while(left < right && !cmp(f[left],key)) left++;
		if(left == right) break;
		T temp = f[left];
		f[left] = f[right];
		f[right] = temp;
	}

	if(cmp(f[left],key)) return start;
	f[start] = f[left];
	f[left] = key;
	return left;
}

template
void QuickSort(vector & f, int start, int finish) { 
	if(start >= finish) return;
	int boundary = Partition(f, start, finish, Cmp);
	QuickSort(f, start, boundary - 1);
	QuickSort(f, boundary + 1, finish);
}


int main() {
	ifstream fin("frac1.in");
	fin>>N;
	fin.close();
	
	for(int i = 1; i <= N; i++) {
		for(int j = 0; j <= i; j++) {
			if(GCD(j, i) == 1) {
				Fraction t;
				t.numerator = j;
				t.denominator = i;
				result.push_back(t);
			}
		}
	}
	
	QuickSort(result, 0, result.size() - 1);


	//
	ofstream fout("frac1.out");
	for(int k = 0; k < result.size(); k++) {
		fout<

他にも考えられます
1. 
任意の2つの点数の差は一定>=1/(160*159)であるため、すべての点数を直接50880に乗じ、四捨五入して直接バケツソートし、入力しながら並べ、分子分母を同時に記録するだけでよい、O(n)!!簡略化も省けたので、同じ値に遭遇したらスキップします(以前は必ずもっと小さい点数がこの値に等しいからです).
2.明らかに、0/i 1/i 2/i...i/iこのシーケンスは、n個のシーケンスを秩序化して集計すればよい(等しければ分母の最小の1つをとる--これは明らかに最も単純な点数である).