F.sorting

sorting.png

Sample Input

2
1 1 1
1 1 2
2
1 1 2
1 1 1
3
1 3 1
2 2 1
3 1 1

Sample Output

2 1
1 2
1 2 3

题意:给定n个元组(a1,b1,c1),(a2,b2,c2),…,(an,bn,cn),将其按(ai+bi)/(ai+bi+ci)的值从小到大排序,输出排序后的n个元组的原序号;
思路:编写sort里的cmp函数(形参为元组结构体元素,设为Tuple x,Tuple y),若直接算出(x.a+x.b)(y.a+y.b+y.c)和(y.a+y.b)(x.a+x.b+x.c)再比较大小,这两个结果会爆unsigned long long;
可以把因式乘积展开成多项式的和,约去两式中相同的项,得到x.ay.c+x.by.c和y.ax.c+y.bx.c,因此只需计算它俩再比较即可,结果不会爆unsigned long long

后AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include "bits/stdc++.h"
using namespace std;
struct node{
long double a,b,c;
int numb;
}ss[1005];

bool cmp(const node &a,const node &b){
long double suma,sumb;
//suma=a.a*b.c+a.b*b.c;
//sumb=b.a*a.c+b.b*a.c;
suma=(a.a+a.b)/(a.a+a.b+a.c);
sumb=(b.a+b.b)/(b.a+b.b+b.c);
if(suma!=sumb)return suma<sumb;
return a.numb<b.numb;
}

int main(){
int n;
while(cin>>n){
for(int i=0;i<n;i++){
cin>>ss[i].a>>ss[i].b>>ss[i].c;
ss[i].numb=i+1;
}
stable_sort(ss,ss+n,cmp);
int i;
for(i=0;i<n-1;i++)
cout<<ss[i].numb<<" ";
cout<<ss[i].numb<<endl;
}
return 0;
}

感谢支持 !
0%