Home > Old Blog Posts > USACO 2.1.2 Ordered Fractions

USACO 2.1.2 Ordered Fractions


水到一个境界的题目。

实现上,每个数都存储分子和分母,判断大小的时候交叉相乘就行了,比除法快很多。(但我比较懒还是用了除法……)

代码:

/*
ID: dementr1
PROG: frac1
LANG: C++
*/
#include<iostream>
#include<fstream>
#include<math.h>
using namespace std;
ifstream fin(“frac1.in”);
ofstream fout(“frac1.out”);
struct frac
{
int a,b;
} sorting[100000];
int num,counter;
int prime[100],n;
bool list[160161]={false};
bool judge(int a)
{
if(a==1) return false;
int i;
for(i=2;i<=(int)sqrt(a);i++)
if(a%i==0) return false;
return true;
}
void create()
{
int i;
for(i=1;i<=n;i++)
if(judge(i)) prime[num++]=i;
}
void work(int *a,int *b)
{
int x=*a,y=*b,i;
for(i=0;i<num;i++)
while(x%prime[i]==0&&y%prime[i]==0)
{
x/=prime[i];
y/=prime[i];
}
*a=x;
*b=y;
}
void working()
{
int i,j;
for(i=1;i<=n;i++)
for(j=0;j<=i;j++)
{
int a=i,b=j;
work(&a,&b);
list[b*1000+a]=true;
}
for(i=0;i<=n*1001;i++)
{
if(list[i])
{
sorting[counter].a=(int)i/1000;
sorting[counter++].b=i%1000;
}
}
}
void swap(frac *a, frac *b)
{
frac x=*a;
*a=*b;
*b=x;
}
int partition(frac A[],int left, int right)
{
int i=(left+right)/2,j;
swap(&A[i],&A[right]);
i=left-1;
for(j=left;j<right;j++)
{
float x=(float)A[j].a/A[j].b,y=(float)A[right].a/A[right].b;
if(x<y)
swap(&A[++i],&A[j]);
}
i++;
swap(&A[i],&A[right]);
return i;
}
void quicksort(frac A[], int left, int right)
{
int i;
if(left<right)
{
i=partition(A,left,right);
quicksort(A,left,i-1);
quicksort(A,i+1,right);
}
}
int main()
{
int i;
fin>>n;
create();
working();
quicksort(sorting,0,counter-1);
for(i=0;i<counter;i++)
fout<<sorting[i].a<<“/”<<sorting[i].b<<endl;
return 0;
}

Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: