Hang Gliding线段树

Hang Gliding线段树

参考文章：​​链接​​​ 题目链接：​​链接​​

题目描述

The 2020 hang gliding world championships are coming to Florida next spring! (You may think it is odd to hold in Florida a sport that requires mountains, but it turns out that hang gliders can be towed to altitude by other aircraft.) The competition is divided into a set of tasks; completing a task successfully gives a pilot a number of points. Either all points are awarded for a task, or none are. For each task, every pilot has a probability of success. A pilot’s score is the total of all successfully completed tasks at the end of the competition. This year, the organizing committee couldn’t decide on a reasonable number of tasks, so the time slots for tasks overlap. At any given time, there can be multiple tasks going on, but a pilot may only choose one to be competing in at that time. Each pilot may compete in as many tasks as they want given this constraint. The pilots know their own strengths and weaknesses, and will choose tasks in order to maximize their expected score. You have been offered free hang gliding lessons if you help with scoring software for the event. Among other things, the committee wants the software to be able to predict the winners ahead of time. Given a set of tasks, each with a time slot and a point score to be awarded for success, and a list of pilots, each with success probabilities for each task, compute the expected score for each pilot, and report the top 3 expected scores.

输入描述

输出描述

Print the top 3 pilots. Print, in order of descending expected score, the pilot’s number, a space, and the pilot’s expected score, rounded to 2 decimal places (i.e., a score of 42.494 would be printed as 42.49; a score of 42.495 would be printed as 42.50). Note that pilots are numbered starting at 1, not zero.

示例

input:

3 3 0 1 51 2 102 3 150.00.00.21.00.00.00.00.750.0

output:

3 7.502 5.001 3.00

input:

3 4 0 3 503 6 500 6 750.20.30.60.60.60.50.60.50.40.90.90.9

output:

4 90.00 2 60.003 55.00

题意

有t个任务，p个人，然后输入t个任务的起止时间和分值 对于每一个人，都对这t个任务有一个得分的概率（对应接下来输入的p个组，每组t个数，对应t个任务当前这个人得分的概率） 当一个任务的结束和另一个任务的开始时间重复的时候，可以在一个任务结束之后立马从事该任务（1-2 后 2-3 是可以的） 对于一个时间段内只能够有一个任务在进行，不能够在同一个时间段内有多个任务同时进行 问得分最高的三个人的编号以及分数

solution

线段树维护区间内已得分数最大值

int t,p;double prob[maxn];struct task{ int s,e,id; double val;}tsk[maxn];struct pilot{ int id; double x;}plt[maxn];struct node{ int l,r; double w;}tree[maxn << 2];bool cmp(task tsk1,task tsk2){ return tsk1.e < tsk2.e;///结束时间从小到大}bool cmp2(pilot plt1,pilot plt2){ return plt1.x > plt2.x;}void PushUp(int rt){ tree[rt].w = max(tree[rt<<1].w,tree[rt<<1|1].w);}void Update(int rt,double w){ tree[rt].w = max(tree[rt].w,w);}void Build(int rt,int l,int r){ tree[rt].l = l; tree[rt].r = r; if(l == r){ tree[rt].w = 0;/// current value set as zero return; } int mid = l + r >> 1; Build(rt<<1,l,mid); Build(rt<<1|1,mid+1,r);///divide PushUp(rt);///push up}void UpdatePnt(int rt,int pos,double w){ if(tree[rt].l == pos && tree[rt].l == tree[rt].r){ ///Update(rt,w);///改掉 tree[rt].w = max(tree[rt].w,w); return; } int mid = tree[rt].l + tree[rt].r >> 1; if(pos <= mid) UpdatePnt(rt << 1,pos,w); else UpdatePnt(rt<<1|1,pos,w); PushUp(rt);}double Query(int rt,int l,int r){ if(tree[rt].l >= l && tree[rt].r <= r) return tree[rt].w; int mid = tree[rt].l + tree[rt].r >> 1; if(r <= mid) return Query(rt << 1,l,r); else if(l > mid) return Query(rt<<1|1,l,r); else return max(Query(rt<<1,l,r),Query(rt<<1|1,l,r));}int main() { t = read,p = read; for(int i=1;i<=t;i++){ cin >> tsk[i].s >> tsk[i].e >> tsk[i].val; tsk[i].id = i; } sort(tsk+1,tsk+1+t,cmp); for(int i=1;i<=p;i++){ for(int j=1;j<=t;j++){ cin >> prob[j]; } /// Build(1,0,maxn); for(itn j=1;j<=t;j++){ double mx = Query(1,0,tsk[j].s); int id = tsk[j].id; UpdatePnt(1,tsk[j].e,tsk[j].val * prob[id] + mx); } plt[i].x = tree[1].w; plt[i].id = i; } sort(plt+1,plt+1+p,cmp2); for(itn i=1;i<=3;i++){ printf("%d %.2f\n",plt[i].id,plt[i].x); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。