题目描述
有序分数
样例
输入样例:
5
输出样例:
0/1
1/5
1/4
1/3
2/5
1/2
3/5
2/3
3/4
4/5
1/1
思路
这个题分两个步骤:
1.找出[0~1]的分数
2.将这些分数从大到小排序
这里因为输出方式是按照“分子/分母”的形式,自然想到用pair
在找分数时,因为会出现重复 如:1/1和5/5,则用一个cnt数组来存分数值
cnt数组在用时会出现下标不知道怎么取
我这里想的是将分数映射到一个整数,这里直接将分数乘一个很大的数字就行,只要把cnt开大一点就可以
排序时因为sort是先按照PII中元素的first从小到大,再在相同first中再按second大小排序
这种情况会导致输出不符合答案要求
则在sort中加一个compare属性即可
C++ 代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int,int>PII;
const int N=1e5+10;
vector<PII>p;
int n;
int cnt[N];
bool compare(PII a,PII b)
{
return (double)a.first / a.second < (double)b.first / b.second;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)//i做分母,j做分子
for(int j=0;j<=i;j++){
int s=(float)j/i *100000;
cnt[s]++;
if((j/i==0 || (j/i==1&&j%i==0))&&cnt[s]==1)
p.push_back({j,i});
}
sort(p.begin(),p.end(),compare);
for(auto ps: p)
{
printf("%d/%d",ps.first,ps.second);
puts("");
}
return 0;
}
欢迎大家交流!!!