AcWing 1360. 有序分数不动脑子最笨做法(哈希 字符串 排序 Pair)
原题链接
简单
我看到题第一想法居然是这样写,太菜了,在此记录一下。
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N = 1e5 + 10,M = 200;
PII nums[N];
unordered_map<string,bool> hashtable;
int n,cnt;
int gcd(int a,int b)
{
while(b)
{
int c = a % b;
a = b;
b = c;
}
return a;
}
void table()
{
for(int u = 1;u <= n;u ++)
for(int i = 0;i <= u;i ++)
{
int t = gcd(u,i),temp_i = i,temp_u = u;
temp_i /= t,temp_u /= t;
string s = "";
s = s + to_string(temp_i) + '/' + to_string(temp_u);
if(hashtable[s] == true) continue;
hashtable[s] = true;
nums[cnt].x = temp_i,nums[cnt ++].y = temp_u;
}
}
bool cmp(PII a,PII b)
{
double ax = a.x,ay = a.y;
double bx = b.x,by = b.y;
return (ax/ay) < (bx/by);
}
int main()
{
cin >> n;
table();
sort(nums,nums + cnt,cmp);
for(int i = 0;i < cnt;i ++)
cout << nums[i].x << '/' << nums[i].y << endl;
return 0;
}