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

1112 KGold

题目

给出N个人在0时刻的财富值M[i]（所有人在0时刻的财富互不相等），以及财富增长速度S[i]，随着时间的推移，某些人的财富值会超越另外一些人。如果时间足够长，对于财富增长最快的人来说，他的财富将超越所有其他对手。

求发生的前10000次超越，分别是谁超过了谁？如果总的超越次数不足10000，则输出所有超越，如果1次超越都不会发生，则输出No Solution。 输出按照超越发生的时间排序，同一时刻发生的超越，按照超越者的编号排序，如果编号也相同，则按照被超越者的编号排序。所有排序均为递增序。

输入

第1行：N，表示人的数量。(1 <= N <= 10000)

第2 - N + 1行：每行2个数，分别是初始的财富值M[i]，和财富增长速度S[i]。(0 <= M[i] <= 10^5, 1 <= S[i] <= 100)

输出

输出前10000次超越，超越者和被超越者的编号。如果总的超越次数不足10000，则输出所有。如果1次超越都不会发生，则输出No Solution。

输出按照超越发生的时间排序，同一时刻发生的超越，按照超越者的编号排序，如果超越者编号也相同，则按照被超越者的编号排序。所有排序均为递增序。

输入样例

4

1 100 2 100 3 1 4 50

输出样例

2 3

1 3 2 4 1 4

代码

#include 
   
    using namespace std;#define esp 1e-9typedef long long ll;int n;struct point {
       double w, s;    int id;    bool operator<(const point &a) const {
           return a.w > w;    }} e[10005];struct Cost {
       double cost;    int id;    bool operator<(const Cost &a) const {
           return a.cost > cost;    }} f[10006];struct node {
       double time;    int idx, idy;    bool operator<(const node &a) const {
           return fabs(a.time - time) < esp ? (a.idx == idx ? a.idy < idy : a.idx < idx) : a.time < time;    }} p;priority_queue
    
      q;int solve(double mid) {
       for (int i = 1; i <= n; i++) {
           f[i].id = i;        f[i].cost = mid * e[i].s + e[i].w;    }    sort(f + 1, f + n + 1);    int ans = 0;    for (int i = 1; i <= n; i++)        if (i < f[i].id) ans += f[i].id - i;    return ans > 10000;}int main() {
       scanf("%d", &n);    for (int i = 1; i <= n; i++) {
           scanf("%lf%lf", &e[i].w, &e[i].s);        e[i].id = i;    }    sort(e + 1, e + n + 1);    double l = 1.0, r = 100000005.0;    while (r - l > 0.00001) {
           double mid = (l + r) / 2;        if (solve(mid)) r = mid;        else l = mid;    }    for (int i = 1; i <= n; i++)        for (int j = 1; j < i; j++) {
               if (e[j].s > e[i].s) {
                   p.time = (e[i].w - e[j].w) * 1.0 / (e[j].s - e[i].s);                if (p.time > esp && p.time < r) {
                       p.idx = e[j].id;                    p.idy = e[i].id;                    q.push(p);                }            }        }    for (int i = 0; i < 10000; i++) {
           if (!q.empty()) {
               printf("%d %d\n", q.top().idx, q.top().idy);            q.pop();        } else break;    }    return 0;}
    
   

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