本文共 1355 字，大约阅读时间需要 4 分钟。

题目链接：

题目描述

筱玛是一个热爱地理的好筱玛。最近，在《地理II》作业本上，筱玛学到了“贝塔指数”的概念：

在经济地理学中，交通的联结度表示交通网络的发达程度，通常用贝塔指数来计算与比较。若用V表示一个交通网络中结点的数量，用E表示边的数量，则贝塔指数的计算方式为：β=EV。

“实践是检验真理的唯一标准”。作为一个热爱地理的好筱玛，她马上就把新学的知识应用到实践当中去。筱玛一口气出了n张交通网络规划图，其中第i张交通网络Gi有Vi个结点和Ei条边。筱玛一眼就看出了哪张图好、哪张图坏。但是作为一个负责任的好筱玛，她必须带领同学们一起进步。因此，她需要你将所有的n张图按照贝塔指数排序，并求出它们各自的贝塔指数在模10^9+7意义下的值。

输入描述

第一行一个整数n，表示交通网络规划图的数量。

输出描述

输出共n行，每行一个数，表示贝塔指数第i大的交通网络的贝塔指数在模10^9+7意义下的值。

输入

1

1 3

输出

3

说明

显然此时β=EV=3。

备注

对于100%的数据，保证1≤n≤2×10^5，1≤Vi,Ei≤10^9。

解题思路

将给定的n个数按照E[i]/V[i]排序，再求逆元即可，注意比较大小时用乘法，不要直接除避免精度误差。

Accepted Code:

#include 
   
    using namespace std;typedef long long ll;const int N = 200010;const int MOD = 1e9 + 7;struct edge {    int v, e;    bool operator < (const edge &S) const {        return 1ll * e * S.v > 1ll * S.e * v;    }}G[N];ll POW(ll a, ll b = MOD - 2, ll c = MOD) {    ll res = 1;    ll base = a % c;    while (b) {        if (b & 1)            res = (res * base) % c;        base = (base * base) % c;        b >>= 1;    }    return res;}int main() {    int n;    scanf("%d", &n);    for (int i = 1; i <= n; i++)        scanf("%d%d", &G[i].v, &G[i].e);    sort(G + 1, G + n + 1);    for (int i = 1; i <= n; i++)        cout << G[i].e * POW(G[i].v) % MOD << endl;    return 0;}
   

转载地址：https://lzyws739307453.blog.csdn.net/article/details/94875071 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！