51NOD1112 KGold

1112 KGold
题目来源： UVALive 5868
基准时间限制：1 秒 空间限制：131072 KB 分值: 40 难度：4级算法题 收藏  关注
给出N个人在0时刻的财富值M[i]（所有人在0时刻的财富互不相等），以及财富增长速度S[i]，随着时间的推移，某些人的财富值会超越另外一些人。如果时间足够长，对于财富增长最快的人来说，他的财富将超越所有其他对手。
求发生的前10000次超越，分别是谁超过了谁？如果总的超越次数不足10000，则输出所有超越，如果1次超越都不会发生，则输出No Solution。
输出按照超越发生的时间排序，同一时刻发生的超越，按照超越者的编号排序，如果编号也相同，则按照被超越者的编号排序。所有排序均为递增序。
Input
第1行：N，表示人的数量。(1 <= N <= 10000)
第2 - N + 1行：每行2个数，分别是初始的财富值M[i]，和财富增长速度S[i]。(0 <= M[i] <= 10^5, 1 <= S[i] <= 100)
Output
输出前10000次超越，超越者和被超越者的编号。如果总的超越次数不足10000，则输出所有。如果1次超越都不会发生，则输出No Solution。
输出按照超越发生的时间排序，同一时刻发生的超越，按照超越者的编号排序，如果超越者编号也相同，则按照被超越者的编号排序。所有排序均为递增序。
Input示例
4
1 100
2 100
3 1
4 50
Output示例
2 3
1 3
2 4
1 4
李陶冶 (题目提供者)

O(n^2)水过
枚举每个超越 放大头堆里
如果大头堆超过1e4个元素 就pop一个
最坏情况下O(log(1e4)*n^2) = O(n^2)

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//#include
using namespace std;
#define ll long long
#define ull unsigned long long
#define pii pair
#define INF 1000000007
#define pll pair
#define pid pairconst int N = 1e4;struct S{double t;int a,b;
}ans[N];bool operator<(const S&x,const S&y){if(x.t==y.t){if(x.a==y.a){return x.belse{return x.aelse{return x.tstruct T{int m,s,idx;
}p[N];bool operator <(const T&a,const T&b){if(a.m==b.m){return a.sreturn a.mvoid slove(int n){sort(p,p+n);priority_queueque;S tmp;for(int i=0;ifor(int j=lower_bound(p+i+1,p+n,p[i])-p;jif(a.s>b.s){double t = (double)(b.m-a.m)/(a.s-b.s);tmp = {t,a.idx,b.idx};if(que.size()==N){if(tmpelse{que.push(tmp);}}}}int idx=0;while(!que.empty()){ans[idx++]=que.top();que.pop();}for(int i=idx-1;i>=0;--i){printf("%d %d\n",ans[i].a,ans[i].b);}
}int main()
{//freopen("/home/lu/Documents/r.txt","r",stdin);//freopen("/home/lu/Documents/w.txt","w",stdout);int n;while(~scanf("%d",&n)){for(int i=0;iscanf("%d%d",&p[i].m,&p[i].s);p[i].idx=i+1;}slove(n);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！