警告
本文最后更新于 2023-07-07，文中内容可能已过时。
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;
}
|
Jian YE
支付宝
微信